Reverse Linked List

https://leetcode.com/problems/reverse-linked-list

# Definition for singly-linked list

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Solution

This problem is very basic yet IMPT. It can be solved both iteratively or recursively.

# Iteration

It's quite IMPT to understand and remember the steps in while loop.

Complexity:

  • time: O(n)O(n)
  • space: O(1)O(1)
def reverseList(self, head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        # store next node
        nxt = curr.next
        # update next of current
        curr.next = prev
        # move prev and curr 1 step forward
        prev = curr
        curr = nxt
    return prev

or could combine the assignments (Python's syntactic sugar):

def reverseList(self, head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

# Recursion (REDO)

There are n nodes in total. Assume nk+1n_{k+1} to nmn_m have been reversed and the curr node is nkn_k:

n1...nk1nknk+1...nnn_1 \rightarrow ... n_{k-1} \rightarrow n_k \rightarrow n_{k+1} \leftarrow ... \leftarrow n_n

Set nk+1n_{k+1}'s next to nkn_k: nkn_k.next.next = nkn_k

Also avoid the cycle by setting nkn_k's next to None: nkn_k.next = None

Note that I set head to curr to avoid confusion. hd is the actual head of reversed linked list.

Complexity:

  • time: O(n)O(n)
  • space: O(n)O(n) due to implicit stack space
def reverseList(self, head: ListNode) -> ListNode:
        curr = head
        # not curr covers the empty input: []
        if not curr or not curr.next:
            return curr
        hd = self.reverseList(curr.next)
        curr.next.next = curr
        curr.next = None
        return hd
Last Updated: 7/19/2020, 3:45:14 PM