Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.
For example, the following doubly linked list should be changed to 2<->4<->8<->10
We strongly recommend to minimize your browser and try this yourself first.
Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.
Below is the implementation of merge sort for doubly linked list.
Python Programming
[pastacode lang=”python” manual=”%23%20Program%20for%20merge%20sort%20on%20doubly%20linked%20list%0A%20%0A%23%20A%20node%20of%20the%20doublly%20linked%20list%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%20%20%20%20%20%20%20self.prev%20%3D%20None%0A%20%0Aclass%20DoublyLinkedList%3A%0A%20%0A%20%20%20%20%20%23%20Constructor%20for%20empty%20Doubly%20Linked%20List%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20merge%20two%20linked%20list%0A%20%20%20%20def%20merge(self%2C%20first%2C%20second)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20first%20linked%20list%20is%20empty%0A%20%20%20%20%20%20%20%20if%20first%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20secon%20linked%20list%20is%20empty%20%0A%20%20%20%20%20%20%20%20if%20second%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%0A%20%0A%20%20%20%20%20%20%20%20%23%20Pick%20the%20smaller%20value%0A%20%20%20%20%20%20%20%20if%20first.data%20%3C%20second.data%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next%20%3D%20self.merge(first.next%2C%20second)%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next.prev%20%3D%20first%0A%20%20%20%20%20%20%20%20%20%20%20%20first.prev%20%3D%20None%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next%20%3D%20self.merge(first%2C%20second.next)%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next.prev%20%3D%20second%0A%20%20%20%20%20%20%20%20%20%20%20%20second.prev%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%0A%20%0A%20%20%20%20%23%20Function%20to%20do%20merge%20sort%0A%20%20%20%20def%20mergeSort(self%2C%20tempHead)%3A%0A%20%20%20%20%20%20%20%20if%20tempHead%20is%20None%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20tempHead%0A%20%20%20%20%20%20%20%20if%20tempHead.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20tempHead%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20second%20%3D%20self.split(tempHead)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Recur%20for%20left%20and%20righ%20halves%0A%20%20%20%20%20%20%20%20tempHead%20%3D%20self.mergeSort(tempHead)%0A%20%20%20%20%20%20%20%20second%20%3D%20self.mergeSort(second)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Merge%20the%20two%20sorted%20halves%0A%20%20%20%20%20%20%20%20return%20self.merge(tempHead%2C%20second)%0A%20%0A%20%20%20%20%23%20Split%20the%20doubly%20linked%20list%20(DLL)%20into%20two%20DLLs%0A%20%20%20%20%23%20of%20half%20sizes%0A%20%20%20%20def%20split(self%2C%20tempHead)%3A%0A%20%20%20%20%20%20%20%20fast%20%3D%20slow%20%3D%20%20tempHead%0A%20%20%20%20%20%20%20%20while(True)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fast.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fast.next.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20fast%20%3D%20fast.next.next%0A%20%20%20%20%20%20%20%20%20%20%20%20slow%20%3D%20slow.next%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20temp%20%3D%20slow.next%0A%20%20%20%20%20%20%20%20slow.next%20%3D%20None%0A%20%20%20%20%20%20%20%20return%20temp%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20Given%20a%20reference%20to%20the%20head%20of%20a%20list%20and%20an%0A%20%20%20%20%23%20integer%2Cinserts%20a%20new%20node%20on%20the%20front%20of%20list%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%201.%20Allocates%20node%0A%20%20%20%20%20%20%20%20%23%202.%20Put%20the%20data%20in%20it%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20node%20as%20head%20and%0A%20%20%20%20%20%20%20%20%23%20previous%20as%20None%20(already%20None)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%0A%20%20%20%20%20%20%20%20%23%204.%20change%20prev%20of%20head%20node%20to%20new_node%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head.prev%20%3D%20new_node%0A%20%20%0A%20%20%20%20%20%20%20%20%23%205.%20move%20the%20head%20to%20point%20to%20the%20new%20node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%0A%20%20%20%20def%20printList(self%2C%20node)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20node%0A%20%20%20%20%20%20%20%20print%20%22Forward%20Traversal%20using%20next%20poitner%22%0A%20%20%20%20%20%20%20%20while(node%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20node.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%0A%20%20%20%20%20%20%20%20print%20%22%5CnBackward%20Traversal%20using%20prev%20pointer%22%0A%20%20%20%20%20%20%20%20while(temp)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.prev%0A%20%0A%23%20Driver%20program%20to%20test%20the%20above%20functions%0Adll%20%3D%20DoublyLinkedList()%0Adll.push(5)%0Adll.push(20)%3B%0Adll.push(4)%3B%0Adll.push(3)%3B%0Adll.push(30)%0Adll.push(10)%3B%0Adll.head%20%3D%20dll.mergeSort(dll.head)%20%20%20%0Aprint%20%22Linked%20List%20after%20sorting%22%0Adll.printList(dll.head)” message=”Python” highlight=”” provider=”manual”/]Output:
Linked List after sorting Forward Traversal using next pointer 3 4 5 10 20 30 Backward Traversal using prev pointer 30 20 10 5 4 3
Time Complexity: Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes Θ(nLogn) time.
Wikitechy Editor
Venkatesan Prabu
