AlgoDaily - Reverse a Linked List

Good evening! Here's our prompt for today.

You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows:

SNIPPET

17 -> 2 -> 21 -> 6 -> 42 -> 10

Write an algorithm for a method reverseList that takes in a head node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length.

You may use the example linked list for testing purposes. Your method will be called as such:

1class Node:
2    def __init__(self, val):
3        self.val = val
4        self.next = None
5
6l1 = Node(1)
7l1.next = Node(2)
8reverse_list(l1)

Constraints

Length of the given LinkedList <= 100000
The nodes will always contain integer values between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx
​
 
def reverse_list(head):
    # fill in this method
​
    return head
​
​
# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
​
​
def create_nodes(head, nodes):
    for val in nodes:
        new_node = Node(val)
        head.next = new_node
        head = new_node
​
​
list1 = Node(3)
nodes1 = [4, 5, 6, 7, 8, 9, 10]
create_nodes(list1, nodes1)
​
list2 = Node(1)
nodes2 = [2, 3, 4, 5, 6, 7, 8]
create_nodes(list2, nodes2)
​
​

We'll now take you through what you need to know.

How do I use this guide?

Let's take the most basic linked list first-- one with two nodes. We need to reverse this.

Seems pretty easy, right? To reverse an entire linked list, simply reverse every pointer. If 1 is pointing at 2, flip it so 2 should point to 1.

Of course, there's complexities that lie ahead. But for now, that's the basis for:

SNIPPET

117 -> 2 -> 21 -> 6 -> 42 -> 10

becoming

SNIPPET

117 <- 2 <- 21 <- 6 <- 42 <- 10

The actual reversal method is actually pretty straightforward, but be aware that it takes some time to reason out. It's easy to get lost, so make sure you draw lots of diagrams.

As this is a problem (reversing an entire linked list) that can be broken up into sub-problems (reverse the pointer between just two nodes), it seems like a good opportunity to use recursion.

There are many ways to do the actual reversal, and we'll cover both an iterative and recursive approach, but the general methodology is as follows:

Begin by creating 3 pointers: newHead, head and nextNode.
1. newHead and nextNode are initialized to null.
2. head starts off pointing to the head of the linked list.
Iterate (or recursively do) through the following process until head is null. This means that the end of the list has been reached:

xxxxxxxxxx
print(list_to_str(reverse_list(l1)))
 
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
​
l1 = Node(1)
l1.next = Node(2)
​
def reverse_list(head):
    prev = None
    nextNode = None
    # we start at head
    current = head
​
    if not head:
        return
​
    while current is not None:
        # store the node to the right to reuse later
        nextNode = current.next
        # set the current node's next to point backwards 
        current.next = prev
        # store the current node, to be used as the new next later
        prev = current
        # the previously right-side node is now processed
        current = nextNode
​
    return prev
​

It's difficult to visualize this chain of events, so let's use comments to visualize it. During the interview, try not to keep it in your head.

Here's a pro-tip: many interviews are conducted online now, so you'll be able to type out things. You can use ASCII-esque linked lists like 1 -> 2 -> 3 to keep the directionality clear. If you're still on a whiteboard, diagram away!

It'll be especially difficult while balancing your nerves and talking to the interviewer. Take advantage of the whiteboard not just to record things, but also to think through potential steps.

Let's walk through it step by step and then look at working code. Let's reverse an extremely basic list, like 8 -> 4. The first line is let nextNode = head.next;, which will store the node to the right.

xxxxxxxxxx
 
nextNode = 4
// 8 -> 4

Then we'll do head.next = newHead;, which will set the current node's next to point backwards.

xxxxxxxxxx
 
nextNode = 4
// <- 8, 4

Now newHead = head; will store the current node, to be used as the new next later.

xxxxxxxxxx
 
newHead = 8
nextNode = 4
// <- 8, 4

Finally, the previously right-side node is now processed:

xxxxxxxxxx
 
newHead = 8
nextNode = 4
// <- 8, 4
         ^
   current node

Now we process the next one with the same steps. nextNode = head.next; will store the node to the right.

xxxxxxxxxx
 
newHead = 8
nextNode = null
// <- 8, 4
         ^
   current node

Again, set the current node's next to point backwards with head.next = newHead;. Recall that newHead is 8! This is where we make the switch:

xxxxxxxxxx
 
newHead = 8
nextNode = null
// <- 8 <- 4
           ^
     current node

Now let's see this all put together in code, with lots of comments for edification!

xxxxxxxxxx
print(list_to_str(l2))
 
class Node:
  def __init__(self, val, next = None):
    self.val = val
    self.next = next
​
​
l1 = Node(8)
l2 = Node(4)
l1.next = l2
​
# start at head, 8
head = l1
# example: 8 -> 4
newHead = None
while head:
  # FIRST PASS
  # store the node to the right
  nextNode = head.next
  # nextNode = 4, still 8 -> 4
  # set the current node's next to point backwards
  head.next = newHead
  # 8 -> null
  # store the current node, to be used as the new next later
  newHead = head
  # newHead = 8
  # the previously right-side node is now processed
  head = nextNode
  # head = 4
​

Does that all make sense? Be sure to go through the iterative approach a few times.

Here's the recursive way to do it. This can also be tricky, especially on first glance, but realize most of the magic happens when it gets to the end.

xxxxxxxxxx
 
class Node:
  def __init__(self, val, next = None):
    self.val = val
    self.next = next
​
l1 = Node(8)
l2 = Node(4)
l1.next = l2
​
def list_to_str(head):
    new_arr = []
    while head:
        new_arr.append(str(head.val))
        head = head.next
    return " -> ".join(new_arr)
​
def reverseList(head):
  if (not head) or (not head.next):
    return head
​
  rest = reverseList(head.next)
​
  head.next.next = head
  head.next = None
  return rest
​
print(list_to_str(l1))

Let's take an easy example of 8 -> 4 again. let rest = reverseList(head.next); takes 4 and calls reverseList on it.

Calling reverseList on 4 will have us reach the termination clause because there is no .next:

1if not head or not head.next:
2  return head

We go up the stack back to when 8 was being processed. rest now simply points to 4. Now notice what happens:

1# remember, head is 8 - it is being processed
2# head.next is 4
3head.next.next = head
4# head.next.next was null since 4 wasn't pointing to anything
5# but now head.next (4) points to 8

And we return 4 - which is pointing to 8. And we can simply extrapolate that to longer linked lists! Note that the recursive approach requires more space because we need to maintain our call stack.

Complexity of Final Solution

Let n be the number of nodes in the linked list. We traverse through all n nodes for O(n) linear time complexity. We reuse the old linked list nodes, so our space complexity is a constant O(1) as we do not allocate any extra space.

One Pager Cheat Sheet

You need to write a reverseList algorithm that takes in a head node as a parameter and reverses a linked list of any length in O(n) time with O(1) space.
To reverse a linked list, simply flip each pointer, so that the next references the previous node.
It takes time and effort to properly reverse a linked list, so be sure to use recursion and draw diagrams to help keep your progress on track.
The general methodology for reversing a linked list involves a combination of iterative and recursive techniques that involve creating and manipulating 3 pointers: newHead, head and nextNode.
Keep track of the interview flow by using online comments or, if on a whiteboard, diagrams to help visualize the sequence of events.
Take advantage of the whiteboard to think through potential steps for reversing an technical term list, and then look at working code.
We will change the node's next reference to point to the previous node, using head.next = newHead;.
Storing the current node in newHead will be used as the next later.
The right-side node is now processed and has become the previous node.
We store the node to the right by setting nextNode = head.next; and repeat the same process with the next node.
We make the switch by setting the current node's next to newHead, which is 8.
We can See how all the key concepts are put together in code, with lots of explaining comments!
The recursive approach to this can be tricky, especially on first glance, but most of the magic happens when it reaches the end.
The reverseList function is called on 4, which reaches the termination clause due to there being no .next.
4 was originally not pointing to anything, but after head.next.next = head it now points back to 8.
We have achieved O(n) linear time complexity and O(1) space complexity when traversing a linked list and reusing the old nodes.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
    print("Nice job, 1/1 tests passed!")
 
# iterative
def reverse_list(head):
    prev = None
    nextNode = None
    current = head
​
    if not head:
        return
​
    while current is not None:
        nextNode = current.next
        current.next = prev
        prev = current
        current = nextNode
​
    return prev
​
​
# recursive
def reverse_list(head):
    if (not head) or (not head.next):
        return head
    rest = reverse_list(head.next)
    head.next.next = head
    head.next = None
​
    return rest
​
​
# Node definition
class Node:
    def __init__(self, val):

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.

Constraints

Try to solve this here or in Interactive Mode.

We'll now take you through what you need to know.

Complexity of Final Solution

One Pager Cheat Sheet

This is our final solution.

Great job getting through this. Let's move on.

Programming Categories

Popular Lessons