trjhtr

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

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.