LC 206, Reverse a linked list

Recursive 1, going from head to tail

The recursive call takes two argument, prev and curr that points to previous and current nodes we are working with. We assume/know that all the nodes before and at prev is already reversed and we will just reverse the current pointer to point at reverse. After the current is reversed, we move on to the next recursive reverse with prev = curr and curr = the original curr next.

The base case is when curr is None, that means we have reached the None terminator. So the prev must point at the last node and all the nodes before the last node is already reversed. So we just return the pointer to the last node, which is assigned to prev.

The last node’s pointer got propagated returned back to the top of call stack and is eventually returned to the main.

        def reverse(prev, curr):            
            if not curr:
                return prev
            next_node = curr.next
            curr.next = prev
            return reverse(curr, next_node)

        new_head = reverse(None, head)
        return new_head

Recursive 2, going from tail to head

In this case, the recursive function has 1 argument, curr, the pointer to the node we are working with. During each call of the recursive function, we assume everything after curr has been reversed. So we need to point the curr.next’s next pointer to curr. Then we also need to point curr.next to Null. We can think that at every level of recursive call, the function assume the current is the last node and need to “clean up” by adding a Null. It also prevents cycles.

    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def reverse(curr):
            if curr.next == None:
                return curr
            new_head = reverse(curr.next)
            curr.next.next = curr
            curr.next = None
            return new_head

        if not head:
            return None
        new_head = reverse(head)
        return new_head

Iterative

In the while loop, we will reverse one node at a time and point it to the previous node.

    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        prev = None
        curr = head
        while curr != None:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev

We will iterate till the current node is at Null and return the previous node.

Bug

I first had:

    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        prev = None
        curr = head
        while curr.next != None:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return curr

Doesn’t deal with empty list

If the linked list is empty, then the head will be None and None doesn’t has .next

The last node is not linked

The while loop will terminate at the last node instead at the Null node. This will let the last node’s next not be updated to pointing at its predecessor node.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax