How To Reverse a LinkedList

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.