1
\$\begingroup\$

Problem from www.interviewbit.com.

Problem : Given a singly linked list, modify the value of first half nodes such that :

1st node’s new value = the last node’s value - first node’s current value

2nd node’s new value = the second last node’s value - 2nd node’s current value, and so on ...

NOTE : If the length L of linked list is odd, then the first half implies at first floor(L/2) nodes. So, if L = 5, the first half refers to first 2 nodes. If the length L of linked list is even, then the first half implies at first L/2 nodes. So, if L = 4, the first half refers to first 2 nodes. Example :

Given linked list 1 -> 2 -> 3 -> 4 -> 5, Return 4 -> 2 -> 3 -> 4 -> 5

as for first node, 5 - 1 = 4 for second node, 4 - 2 = 2

Try to solve the problem using constant extra space.

This is my solution on the website's shell. How can this code be better?

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 # @param A : head node of linked list
 # @return the head node in the linked list
 def subtract(self, A):
 if not A.next:
 return A
 fast = A
 slow = A
 prev = None
 cnt = 0 
 # reach till half 
 while fast and fast.next:
 fast = fast.next.next
 slow = slow.next
 cnt += 1
 if fast:
 start = slow.next
 else:
 start = slow
 #reverse the latter half
 while start: 
 temp = start.next
 start.next = prev
 prev = start
 start = temp
 firstA = A
 lastA = prev
 prev1 = prev 
 currA = A
 # modify values of first half
 while cnt: 
 currA.val = lastA.val - firstA.val
 firstA = firstA.next
 lastA = prev.next
 prev = prev.next
 currA = currA.next
 cnt -= 1
 # reverse the list again
 new_prev =None
 while prev1:
 temp = prev1.next
 prev1.next = new_prev
 new_prev = prev1
 prev1 = temp
 return A
asked Jun 9, 2018 at 18:09
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

More functions, please.

Every time you feel compelled to comment a block of code, consider factoring it out into a properly named function. For example,

def subtract(A):
 start = reach_till_half(A)
 prev = reverse(start)
 modify(A, prev)
 reverse(prev)

Of course names could (and should) be better.

answered Jun 9, 2018 at 18:38
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.