[Interview Question] Reverse A Linked List

by

[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 head of a singly linked list, reverse the list, and return 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).

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.
The Complete Guide to PyCharm

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