Reverse Linked List

Reverse Linked List is easier to approach with a clear overview and reliable steps. This guide organizes the essential information, highlights practical details, and explains what to check along the way.

I. Reverse Linked List

A fairly common "beginning" question asked at large companies such as Google, Facebook, Uber,. Is to reverse a singly linked list. It can be said that this is a classic question on the topic of Linked List. In this article, I will give 2 ways to solve the problem and analyze its space and time complexity. I will assume that you already know about the linked list data structure when reading this article. If not, you can read the document "Basic linked list" by Stanford University, USA here.

II. Topic

Write a function that takes as input the head of a Singly Linked List, reverses it and returns the head of the reverse linked list.

This is the implementation of Linked List that I will use in the article:

Sample Input:

head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 # the head node with value 0

Sample output:

head = 5 -> 4 -> 3 -> 2 -> 1 -> 0

You will find many solutions to this problem, but in this article I will only give two that I think are the most typical.

1. Solution 1: Use List as Intermediary

Because a singly linked list can only traverse in one direction (forward) while a list can reverse itself and traverse in both directions (forward, reversed) easily. So the solution that many people have when encountering this problem is to convert the linked list to a list, reverse that list, and then rebuild the linked list using the reversed list. Below is a description of my solution:

Illustration of the solution using list.

And here is my solution:

1.1 Space and Time Complexity Analysis

Note: n is the number of nodes of the input linked list.

Space complexity is O(n):

• The space complexity of constructing a list of n elements from a linked list is O(n).
• The space complexity of constructing a linked list from a list of n elements is O(n).
• Therefore, the space complexity of this solution is O(n).

Time complexity is O(n):

• The time complexity of constructing a list of n elements from a linked list is O(n).
• The time complexity of constructing a linked list from a list of n elements is O(n).
• Therefore, the time complexity of this solution is O(n).

2. Solution 2: Swap Nodes In-place

The solution will be illustrated by the following doodle:

Illustration of how to solve swapping nodes.

The explanation of the solution is as follows:

• We save the positions of 3 nodes in the linked list (previous, current and following).

• Attach the next node of current to previous.

• Then we move the position of 3 nodes (current ? previous, following ? current, current.next -> following) and then attach the next node of current to previous.

• Just repeat the above steps until we reach the end of the linked list and we have completed reversing a linked list.

And here is my solution:

class LinkedList: def __init__(self, value): 
         self.value = value 
         self.next = None 

def reverseLinkedList(head): 
     previous_node, current_node = None, head 
     while current_node: 
         following_node = current_node.next 
         current_node.next = previous_node 
         previous_node, current_node = current_node, following_node 
     return previous_node

2.2 Space and Time Complexity Analysis

Note: n is the number of nodes of the input linked list.

Space complexity is O(1)

• With this solution, we only swap nodes in the input linked list - no additional space is generated.
• Therefore, the total space complexity is O(1).

Time complexity is O(n):

• Time complexity to iterate through nodes in linked list is O(n).
• Therefore, the total time complexity is O(n).

The above two solutions are not all the ways to reverse a linked list but they are two typical ways for this classic problem. Hopefully this blog post can help you in some way. Please share it so that more people know about it and look forward to more of my blog posts on the topic of Data Structure & Algorithm on this guide's tech blog if you find the blog post interesting!

Final Thoughts

The most reliable way to handle reverse linked list is to follow the process in order, verify each important setting, and test the result before moving on. Use the guidance above as a practical reference, then adjust the details for your device, software version, or specific goal.