How To Reverse a LinkedList

Jul 5, 2021

Imagine we have the following data structure for a node in a Linked List.

1
class LinkedList:
2
    def __init__(self, value):
3
        self.value = value
4
        self.next = None
5

6

7
# return the head of the new linked list
8
def reverseLinkedList(head):
9
    # go!

We start out with a linked list like this

None   0 -> 1 -> 2 -> 3 -> 4 -> 5
prev   A    B

The variable head points at 0.

There are a few constraints when solving this problem

Your solution should absolutely be O(n)
Use as few variables as possible - management of the pointers is what makes this problem challenging

Walking through each iteration helped me.

# after 1 iteration
None <- 0    1 -> 2 -> 3 -> 4 -> 5
      prev   A    B

We set A.next to prev, then iterate forward. The variable B really just exists so we can iterate forward once we point A.next elsewhere.

# after 2 iterations
None <- 0 <- 1    2 -> 3 -> 4 -> 5
            prev  A    B

# after 3 iterations
None <- 0 <- 1 <- 2    3 -> 4 -> 5
                 prev  A    B

# after 4 iterations
None <- 0 <- 1 <- 2 <- 3    4 -> 5
                      prev  A    B

# after 5 iterations
None <- 0 <- 1 <- 2 <- 3 <- 4    5
                           prev  A    B

# after 6 iterations
None <- 0 <- 1 <- 2 <- 3 <- 4 <- 5    None None
                                 prev  A    B

Note that prev now points at the new head.

Here’s the final solution.

1
class LinkedList:
2
    def __init__(self, value):
3
        self.value = value
4
        self.next = None
5

6

7
def reverseLinkedList(head):
8
    prev = None
9
    a = head
10
    b = a.next
11

12
    while a is not None:
13
        a.next = prev
14

15
        prev = a
16
        a = b
17
        b = b.next if b is not None else None
18

19
    return prev

You can get rid of the if b is not None else None section if you rearrange the order in which you set everything (you set b = a.next before you do a.next = prev, but honestly I find that harder to reason about.

This solution has O(n) time complexity and O(1) space complexity.

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.