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