Reverse a singly linked list

Given a pointer to the head of a linked list, the task is to reverse the linked list.

Example:
Original: 
1 -> 2 -> 3 -> 4 -> NULL
Reversed: 
4 -> 3 -> 2 -> 1 -> NULL

There are various methods through which this problem can be solved. 

Method 1: Use an auxiliary data structure such as array

1. Traverse the complete list once 
2. Store the data values of each node in an array.
3. Reverse the array elements.
4. Traverse the linked list again and update the data with new array data.

This is a possible solution but not the best one to choose because:
1. The array will make space complexity O(n).
2. There will be more than one traversal of the linked list which can be improved.
3. The linked list node may contain complex data. For example:
1
2
3
4
5
6
7
8
9
class Node:
    def __init__(self, name, age, salary):
        # 3 data values
        self.name = name
        self.age= age
        self.salary = salary
            
        # pointer to next node
        self.next = None
In this example copying data of each node into an array will not be possible. 
And it will be a tedious process to updated each data value for each node.

Hence it is best to rather update the next pointer of each node to reverse the list rather than updating the data part.

Method 2: Iterative method

We try to update the next pointers of each node in a single traversal.
We cannot traverse back in a singly linked list as we only have the next pointers.
Hence at each step, we need to store the previous node so that we can update the current node's next pointer to point to the previous node.

Also, we need to store the next node in a pointer because once we update the current node to point to the previous node our link to the next node will be broken.

Code in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# Python iterative program to reverse a singly linked list
 
 
# Node class
class Node:
 
    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None
 
 
class SinglyLinkedList:
 
    # Constructor to initialise head
    def __init__(self):
        self.head = None
 
    # Function to reverse a linked list
    def reverse(self):
 
        # If linked list is empty
        if self.head is None:
            return None
 
        current = self.head
        prev = None
 
        while current is not None:
            # Store the value of current.next
            next = current.next
            # Set current.next to point to the previous node
            current.next = prev
            # Update pointers for next iteration
            prev = current
            current = next
 
        self.head = prev
 
    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node
 
    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')
 
# Main code:
linked_list = SinglyLinkedList()
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
 
linked_list.print_data()
 
# call the reverse function
linked_list.reverse()
 
# print the reversed list
linked_list.print_data()
 
"""
Outputs:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None
7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> None
"""

Method 3: Recursive

Generally, you would end up making easy to understand code using recursion in singly linked lists by passing relevant pointers in each function call.

If in each function call we pass the previous node, current node and the head of the list, we will be able to reverse the linked list recursively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def reverseUtil(self, curr, prev):
      
    # If curr is last node then update the head
    if curr.next is None :
        self.head = curr
          
        # Update next to prev node
        curr.next = prev
        return
      
    # Save curr.next node for recursive call
    next = curr.next
 
    # update next to point to previous node
    curr.next = prev
    # make recursive call with next node as curr, and curr node as prev
    self.reverseUtil(next, curr)
 
 
# This function mainly calls reverseUtil()
# with previous as None
def reverse(self):
    if self.head is None:
        return
    self.reverseUtil(self.head, None)

Time and Space Complexity:

The recursive approach is not as efficient as iterative because the recursion stack is used for recursion.

But otherwise, the time complexity of both the iterative and recursive solution is O(n) and that too in a single traversal.

If we ignore the recursion stack the space complexity of iterative and recursive solution is O(1), that is, constant.

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal

Comments

Popular posts from this blog

Sorted Array: Binary Search

Segregate Even Odd value nodes in a linked list

What is 3 Algorithms Per Week?