Subtract first and last nodes of linked list

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


1 Answer

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.