Leetcode 206 - Reverse Linked List

Problem

Leetcode 206. Reverse Linked List

Example:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input: head = [1,2]
Output: [2,1]

Approach

Since all we need to do is reverse the linked list, we can iterate through the list and reverse the direction of the pointers using temp node and a variable to store the previous node. Then we 3 way trade the temp, current node, and previous node. It will make more sense when we draw it out.

Visual representation of the approach:

list = None -> 1 -> 2 -> 3 -> 4 -> 5 -> None
prev = None
temp = None

Since curr is not None, we can enter the loop.

list = None -> 1 -> 2 -> 3 -> 4 -> 5 -> None
prev = None
curr =         1
temp =              2

list = None <- 1    2 -> 3 -> 4 -> 5 -> None
prev =         1
curr =              2
temp =                   3

list = None <- 1 <- 2    3 -> 4 -> 5 -> None
prev =              2
curr =                   3
temp =                        4

list = None <- 1 <- 2 <- 3    4 -> 5 -> None
prev =                   3
curr =                   4
temp =                        5

list = None <- 1 <- 2 <- 3 <- 4    5 -> None
prev =                        4
curr =                             5
temp =                                  None

list = None <- 1 <- 2 <- 3 <- 4 <- 5    None
prev =                             5
curr =                                  None
temp =                                  None

Since curr is None, we exit the loop and return prev as it is now the head of the reversed linked list.

Here is the implementation of the approach:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

Time Complexity and Space Complexity

The time complexity is $ O(n) $ because we iterate through the list once.

The space complexity is $ O(1) $ because we are not using any extra space.