To approach this problem, let's start with a concrete understanding of how a linked list works. Unlike an array, a linked list is a recursive data structure - each node points to another node - which means we don't have random access to its members. Instead, we're given a head node with a
next property that points to the subsequent node in the list. Here's an example of a linked list with two nodes:
class Node: def _init_(self, value=None): self.value = value self.next = None n1 = Node(1) n2 = Node(2) n1.next = n2
1class Node: 2 def _init_(self, value=None): 3 self.value = value 4 self.next = None 5 6n1 = Node(1) 7n2 = Node(2) 8n1.next = n2
If this list were to be reversed, its clear that
n2 would point to
n1. But what would
n1 point to? Recall that while
n2 does not have a child, the node's
next property still exists - it simply points to
null. And while there is no node pointing to
n1, we can imagine that its parent is
n1 would point to
We can imagine a
null node at the head and the tail of the list.
At minimum, reversing a linked list will require updating each node's
next pointer to reference its parent. Since we'll need to visit each node at least once, our solution space is limited to a linear traversal.
Let's explore how we can update each node in-place with a single traversal. A linked list can be traversed recursively or iteratively - in both approaches, we maintain a reference to the current node, its parent, and its child, and re-assign the
next reference for each node.
Since a linked list is an inherently recursive data structure, it makes sense to consider a post-order recursive traversal to reverse the list. Why "post-order"? The key here is to recurse on each subsequent node until the last node is reached, and then update the next pointers as each execution pops off the call stack.
Each call to
reverse_list is passed in a reference to the current node's child, which adds a new execution frame to the call stack.
null node is reached (our base case), we begin the reassignment process. As each context is popped off the stack, we assign the current node's child's
next pointer to the current node, effectively reversing its reference. Then return the reversed list so far.
We also set the current node's
next pointer to
null - this will be overwritten once the subsequent recursive call is resolved, except for the original head which is now the tail and therefore has no
class Solution: def reverse_list(curr_node: Node) -> Node: if not curr_node or not curr_node.next: return curr_node prev = self.reverse_list(curr_node.next) curr_node.next.next = curr_node curr_node.next = None return prev
1class Solution: 2 def reverse_list(curr_node: Node) -> Node: 3 if not curr_node or not curr_node.next: 4 return curr_node 5 6 prev = self.reverse_list(curr_node.next) 7 curr_node.next.next = curr_node 8 curr_node.next = None 9 return prev
O(n) (Recursion requires linear space on the call stack to maintain a reference to each execution context.)
Reversing a linked list iteratively is more space efficient than recursion, and tends to be more easy to grasp.
The task of any iterative traversal is managing pointers across iterations. First, let's set up our state-of-the-world for the head (input) node.
prev points to
null (the head has no parent),
curr points to the current node (the head), and, if there is indeed a current node,
temp_next points to the current node's child.
At each itertion, we assign the current node's
next pointer to the node at
prev (reversing the reference). We then iterate forward by pointing
prev to the current node and
curr to the original
We continue this process until a
null child is reached - at which point we can return the most recent
prev node which is our new head.
class Solution: def reverse_list(self, node: Node) -> Node: prev = None curr = node while curr: temp_next = curr.next curr.next = prev prev = curr curr = temp_next return prev
1class Solution: 2 def reverse_list(self, node: Node) -> Node: 3 prev = None 4 curr = node 5 6 while curr: 7 temp_next = curr.next 8 curr.next = prev 9 prev = curr 10 curr = temp_next 11 12 return prev
Given a list of tuples that represent (X, Y) coordinates on an XY plane and an integer K, return a list of the K-closest points to the origin (0, 0).
Given a lexicographically sorted list of words, return the order of the alphabet. Also seen as: Given a list of lists in a lexigraphic ordering, return the ordering of the characters in the language.
Given a string `s`, find the length of the longest substring without repeating characters.
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.