Skip to content
Advertisement

Reversing a linked list(Iterative method)

I am writing a code for reversing a linked list in python. The following code does not pass the test case:

class ListNode(object):
    def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution(object):
    def reverseList(self, head)    
        prev, curr = None, head
        while curr:
            curr.next = prev
            prev = curr 
            curr = curr.next
        return prev

while this code passes:

class Solution(object):        
    def reverseList(self, head):  # Iterative
        prev, curr = None, head
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        return prev

What is the difference between the two?

Advertisement

Answer

In your unrolled code, by the time you get to the last line, curr.next has been overwritten with prev. It no longer has its original value. Both prev and curr will point to the old prev.

User contributions licensed under: CC BY-SA
10 People found this is helpful
Advertisement