0
\$\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
\$\endgroup\$
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.