[toc]

?οΈ **Company Tags:** As reported by numerous programmers across the globe, this question has been asked in coding interviews/rounds by companies like-

**Amazon****Accolite****Adobe****Cisco****Cognizant****Goldman Sachs****VMWare**

So, if you are preparing for your upcoming coding interview, then you might well come across this question in your coding round. Can you solve it?

## Problem Formulation

**Given **the

of a singly linked list, reverse the list, and return `head`

*the reversed list*.

**β οΈConstraints:** The number of nodes in the list is the rangeΒ `[0, 5000]`

?**Challenge: **Can you implement an iterative solution and a recursive solution?

**?**Examples

Letβs have a look at some examples to improve our understanding of this problem.

**Example 1:**

Input:head = [1,2,3,4,5]Output:[5,4,3,2,1]

**Example 2:**

Input:head = [1,2]Output:[2,1]

**Example 3:**

Input:head = []Output:[]

**?οΈ** Solution 1: Iterative Approach

In this solution, you will learn how to reverse the given linked list **iteratively**.

**Approach: ** The idea is to traverse the list and change the current node’s next pointer to point to its previous element. A node does not have a reference to its previous node. Hence, you have to store the previous element beforehand. You need another pointer that stores the next node before you the reference.

In simple terms, you will need three-pointers:

**current_node**β points to the current node.**previous_node**β points to the trailing/previous node to the current node.**next_node**β points to the next node to the current node.

Reverse the current_node pointer in each step and then advance with all three to the next node. Finally, return the new head reference at the end.

**Lets have a look at the code:**

def reverse_list(self, head): previous_node = None current_node = head while current_node: next_node = current_node.next current_node.next = previous_node previous_node = current_node current_node = next_node head = previous_node return head

**Explanation:**

Let’s understand the code with the help of an illustration. Consider that the given list is `[1,2,3]`

.

- You have to begin by initializing the
**previous_node**and**next_node**pointers. - Once the pointers have been initialized, the next phase is to iterate through the entire list and reverse it. Let’s visualize what happens in every iteration:

**1st Iteration**

**2nd Iteration**

**3rd Iteration**

**Test Cases:**

The entire code to execute and check the test cases upon the given approach can be found here: **Reverse A Linked List In Python**.

**Complexity Analysis:** Assuming that the length of the list is **n**, the for loop undergoes n iterations. Thus, the iterative solution has a runtime complexity of **O(n)**.

**?οΈ** Solution 2: Recursive Approach

In the second solution, you will learn how to solve the given problem using a recursive approach.

**Approach: **This approach is slightly trickier than the iterative solution. The idea here is, to begin with the **node** (head) and shift the pointers one by one using the function recursively. Finally, when the base case is reached, you have to return the new head reference at the end.

**Algorithm:**

- Start with the head node.
- If the current node’s next element is null, return the current node.
- Otherwise, recursively traverse the list.
- Ensure that in every function call, you reverse the next pointer of the current element to the previous element of the list. i.e.,
`node.next = prev`

and then call the recursive function again i.e.,`reverse_list(n, node)`

.

- Ensure that in every function call, you reverse the next pointer of the current element to the previous element of the list. i.e.,

Let’s have a look at the code to implement the above concept.

def reverse_list(self, node, prev=None): if not node: return prev n = node.next node.next = prev return self.reverse_list(n, node)

**Explanation:**

Let’s understand the code with the help of an illustration. Consider that the given list is `[1,2,3]`

. To make things easy to understand and grasp the concept, here’s a graphical illustration of each step that occurs in our code.

The following diagram represents the initial position of pointers and variables/references within the linked list.

**Round 1**

- During the first function call,
**node**is made to point to the currnent element, i.e.,`[1]`

, while**n**is made to point to the next element, i.e.,`[2]`

. - The next pointer to the current node is then reversed by pointing it to the previous element as
`node.next = prev`

which is`None`

in the first case. - Finally, the function is called again such that the arguments passed to the function are as follows
`reverse_list([2], [1])`

.

**Round 2**

- During the second function call,
**node**points at`[2]`

which is the current node now, while**n**is made to the next element, i.e.,`[3]`

. - The next pointer to the current node is then reversed by pointing it to the previous element as
`node.next = prev`

which is`[1]`

in this case. - Finally, the function is called again such that the arguments passed to the function are as follows
`reverse_list([3], [2])`

.

**Round 3**

- During the second function call,
**node**points at`[3]`

which is the current node now, while**n**is made to the next element, which now becomes`[None]`

. This indicates we are on the verge of reaching the base case. - The next pointer to the current node is then reversed by pointing it to the previous element as
`node.next = prev`

which is`[2]`

in this case. - Finally, the function is called again such that the arguments passed to the function are as follows
`reverse_list([none], [3])`

.

**Round 4**

- The value of node is now [None]. You, we have reached the base case. Thus, return the new head reference of the reversed list which is given by
`prev`

in this case.

**Test Cases:** The entire code to execute and check the test cases upon the given approach can be found here: **Reverse A Linked List In Python**

**Complexity Analysis:** Assume that **n** is the length of the given linked list. The above approach requires **n+1 **function calls to reach the desired output. Hence the time complexity of this approach is **O(n+1) **~ **O(n)**.

## Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and **subscribe** for more interesting coding problems.

**Recommended: ** **Finxter Computer Science Academy**

- Do you want to master the most popular Python IDE fast?
- This course will take you from beginner to expert in PyCharm in ~90 minutes.
- For any software developer, it is crucial to master the IDE well, to write, test and debug high-quality code with little effort.

**Join the PyCharm Masterclass** now, and master PyCharm by tomorrow!