Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 …
You are required to do this in place without altering the nodes’ values.
Examples:
Input: 1 -> 2 -> 3 -> 4 Output: 1 -> 4 -> 2 -> 3 Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3
Simple Solution:
1) Initialize current node as head.
2) While next of current node is not null, do following
a) Find the last node, remove it from the end and insert it as next
of the current node.
b) Move current to next to next of current
The time complexity of the above simple solution is O(n2) where n is the number of nodes in the linked list.
Better Solution:
1) Copy contents of the given linked list to a vector.
2) Rearrange the given vector by swapping nodes from both ends.
3) Copy the modified vector back to the linked list.
Implementation of this approach: https://ide.neveropen.co.uk/1eGSEy
Thanks to Arushi Dhamija for suggesting this approach.
Efficient Solution:
1) Find the middle point using tortoise and hare method. 2) Split the linked list into two halves using found middle point in step 1. 3) Reverse the second half. 4) Do alternate merge of first and second halves.
The Time Complexity of this solution is O(n).
Below is the implementation of this method.
Python3
# Python program to rearrange linked list # in place # Node Class class Node: # Constructor to create # a new node def __init__(self, d): self.data = d self.next = None def printlist(node): if(node == None): return while(node != None): print(node.data," -> ", end = "") node = node.next def reverselist(node): prev = None curr = node next=None while (curr != None): next = curr.next curr.next = prev prev = curr curr = next node = prev return node def rearrange(node): # 1) Find the middle point using # tortoise and hare method slow = node fast = slow.next while (fast != None and fast.next != None): slow = slow.next fast = fast.next.next # 2) Split the linked list in # two halves # node1, head of first half # 1 -> 2 -> 3 # node2, head of second half # 4 -> 5 node1 = node node2 = slow.next slow.next = None # 3) Reverse the second half, # i.e., 5 -> 4 node2 = reverselist(node2) # 4) Merge alternate nodes # Assign dummy Node node = Node(0) # curr is the pointer to this # dummy Node, which will be # used to form the new list curr = node while (node1 != None or node2 != None): # First add the element from # first list if (node1 != None): curr.next = node1 curr = curr.next node1 = node1.next # Then add the element from # second list if(node2 != None): curr.next = node2 curr = curr.next node2 = node2.next # Assign the head of the new list # to head pointer node = node.next head = Nonehead = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) # Print original list printlist(head) # Rearrange list as per ques rearrange(head) print() # Print modified list printlist(head) # This code is contributed by ab2127 |
Output:
1 -> 2 -> 3 -> 4 -> 5 1 -> 5 -> 2 -> 4 -> 3
Time Complexity: O(n)
Auxiliary Space: O(1)
Thanks to Gaurav Ahirwar for suggesting the above approach.
Another approach:
1. Take two pointers prev and curr, which hold the addresses of head and head-> next.
2. Compare their data and swap.
After that, a new linked list is formed.
Below is the implementation:
Python3
# Python3 code to rearrange linked list # in place class Node: def __init__(self, x): self.data = x self.next = None # Function for rearranging a # linked list with high and # low value def rearrange(head): # Base case if (head == None): return head # Two pointer variable prev, curr = head, head.next while (curr): # Swap function for swapping # data if (prev.data > curr.data): prev.data, curr.data = curr.data, prev.data # Swap function for swapping data if (curr.next and curr.next.data > curr.data): curr.next.data, curr.data = curr.data, curr.next.data prev = curr.next if (not curr.next): break curr = curr.next.next return head # Function to insert a node in the # linked list at the beginning def push(head, k): tem = Node(k) tem.data = k tem.next = head head = tem return head # Function to display node of # linked list def display(head): curr = head while (curr != None): print(curr.data, end = " ") curr = curr.next # Driver code if __name__ == '__main__': head = None # Let create a linked list # 9 . 6 . 8 . 3 . 7 head = push(head, 7) head = push(head, 3) head = push(head, 8) head = push(head, 6) head = push(head, 9) head = rearrange(head) display(head) # This code is contributed by mohit kumar 29 |
Output:
6 9 3 8 7
Time Complexity : O(n)
Auxiliary Space : O(1)
Thanks to Aditya for suggesting this approach.
Another Approach: (Using recursion)
- Hold a pointer to the head node and go till the last node using recursion
- Once the last node is reached, start swapping the last node to the next of head node
- Move the head pointer to the next node
- Repeat this until the head and the last node meet or come adjacent to each other
- Once the Stop condition met, we need to discard the left nodes to fix the loop created in the list while swapping nodes.
Python3
# Python3 program to implement # the above approach class Node: def __init__(self, key): self.data = key self.next = None left = None # Function to print the list def printlist(head): while (head != None): print(head.data, end = " ") if (head.next != None): print("->", end = "") head = head.next print() # Function to rearrange def rearrange(head): global left if (head != None): left = head reorderListUtil(left) def reorderListUtil(right): global left if (right == None): return reorderListUtil(right.next) # We set left = null, when we # reach stop condition, so no # processing required after that if (left == None): return # Stop condition: odd case : # left = right, even # case : left.next = right if (left != right and left.next != right): temp = left.next left.next = right right.next = temp left = temp else: # Stop condition , set null # to left nodes if (left.next == right): # Even case left.next.next = None left = None else: # Odd case left.next = None left = None # Driver code head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) # Print original list printlist(head) # Modify the list rearrange(head) # Print modified list printlist(head) # This code is contributed by patel2127 |
Output:
1 ->2 ->3 ->4 ->5 1 ->5 ->2 ->4 ->3
Time Complexity: O(n), where n represents the length of the given linked list.
Auxiliary Space: O(n), for recursive stack where n represents the length of the given linked list.
Please refer complete article on Rearrange a given linked list in-place. for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
