Good morning! 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:
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
and1000000000
- 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:
117 -> 2 -> 21 -> 6 -> 42 -> 10
becoming
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
andnextNode
.newHead
andnextNode
are initialized tonull
.head
starts off pointing to the head of the linked list.
- Iterate (or recursively do) through the following process until
head
isnull
. 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 ahead
node as a parameter and reverses a linked list of any length inO(n)
time withO(1)
space. - To reverse a linked list, simply
flip
each pointer, so that thenext
references theprevious
node. - It takes time and effort to properly
reverse
a linked list, so be sure to userecursion
and draw diagrams to help keep your progress on track. - The general methodology for reversing a linked list involves a combination of
iterative
andrecursive
techniques that involve creating and manipulating 3 pointers:newHead
,head
andnextNode
. - 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 termlist, and then look at working code
.- We will change the node's
next
reference to point to the previous node, usinghead.next = newHead;
. - Storing the current node in
newHead
will be used as thenext
later. - The right-side node is now
processed
and has become the previous node. - We
store the node to the right
by settingnextNode = head.next;
and repeat the same process with the next node. - We make the switch by setting the current node's
next
tonewHead
, which is8
. - 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 on4
, which reaches the termination clause due to there being no.next
. 4
was originally not pointing to anything, but afterhead.next.next = head
it now points back to8
.- We have achieved
O(n)
linear time complexity andO(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.