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.
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:
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.
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
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 |
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
Post a Comment