EASY

DATA STRUCTURES AND ALGORITHMS

LINKED LISTS

Written By

Tom Wagner

Kenny Polyak

Introduction Reverse Linked List

The Reverse Linked List problem involves reversing the order of elements in a linked list, a data strucutre where a each node is connected to the subsequent node with a pointer. The goal of this problem is to traverse the linked list while reversing the order of the pointers that link the nodes together.

Problem Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

**Input:** [1,2,3,4,5]

**Output:** [5,4,3,2,1]

**Input:** [1,2]

**Output:** [2,1]

**Input:** [1]

**Output:** [1]

**Constraints**

- The number of nodes in the list is in the range [0, 5000].
- -5000 <= Node.value <= 5000

Solution Reverse Linked List

Watch Someone Solve Reverse Linked List

Snap InterviewC++ Interview

Advance this person to the next round?

Technical Skills:

3/4

Problem Solving Ability:

4/4

Communication Ability:

4/4

Show Transcript

Snap InterviewPython Interview

Advance this person to the next round?

Technical Skills:

3/4

Problem Solving Ability:

4/4

Communication Ability:

3/4

Show Transcript

Watch more mock interviews

Let's start our approach 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
```

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 `null`

. So `n1`

would point to `null`

.

Caption: 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 linear traversal. A linked list can be traversed both recursively and 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.

Once a `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 `next`

node.

```
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 prev = self.reverse_list(curr_node.next)
6 curr_node.next.next = curr_node
7 curr_node.next = None
8 return prev
```

- Time Complexity:
`O(n)`

- Space Complexity:
`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 `next`

node.

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 while curr:
6 temp_next = curr.next
7 curr.next = prev
8 prev = curr
9 curr = temp_next
10 return prev
```

- Time Complexity:
`O(n)`

- Space Complexity:
`O(1)`

MEDIUM

Data Structures and Algorithms

Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

HEAPSTREES

Watch 1 interview

MEDIUM

Mathematics

Reverse Integer

Given a 32-bit signed integer, reverse digits of the integer.

STRINGS

Watch 1 interview

MEDIUM

Data Structures and Algorithms

Find Peak Element

Given a two-dimensional binary matrix where 1 represents water and 0 represents land, mutate the matrix in place and return the matrix with the highest peak maximized.

ARRAYSSORTINGMAPSSEARCH

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.

Interview prep and job hunting are chaos and pain. We can help. Really.