Reverse Linked List

problem at:

# Definition for singly-linked list

class ListNode:
    def __init__(self, x):
        self.val = x = 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.


  • time:
  • space:
def reverseList(self, head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        # store next node
        nxt =
        # update next of current = 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:, prev, curr = prev, curr,
    return prev

# Recursion (REDO)

There are n nodes in total. Assume to have been reversed and the curr node is :

Set 's next to : =

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

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


  • time:
  • space: due to implicit stack space
def reverseList(self, head: ListNode) -> ListNode:
        curr = head
        # not curr covers the empty input: []
        if not curr or not
            return curr
        hd = self.reverseList( = curr = None
        return hd