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

The important change here is to modify the previous pointers also when merging two lists.

Doubly Linked List:

Doubly Linked List (DLL) is a list of elements and it varies from Linked List. It allows navigation, either forward or backward when compared to Single Linked List. It has two pointers: previous pointer and next pointer. Every element points to next of the list and previous element in list.

Terms used in doubly linked list:

  • Link
  • Next
  • Prev
  • Linked list

C Programming to implement of merge sort for doubly linked list:

[pastacode lang=”c” manual=”%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%2C%20*prev%3B%0A%7D%3B%0A%20%0Astruct%20node%20*split(struct%20node%20*head)%3B%0A%20%0A%0Astruct%20node%20*merge(struct%20node%20*first%2C%20struct%20node%20*second)%0A%7B%0A%0A%20%20%20%20if%20(!first)%0A%20%20%20%20%20%20%20%20return%20second%3B%0A%20%0A%0A%20%20%20%20if%20(!second)%0A%20%20%20%20%20%20%20%20return%20first%3B%0A%20%0A%20%20%20%20%0A%20%20%20%20if%20(first-%3Edata%20%3C%20second-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20first-%3Enext%20%3D%20merge(first-%3Enext%2Csecond)%3B%0A%20%20%20%20%20%20%20%20first-%3Enext-%3Eprev%20%3D%20first%3B%0A%20%20%20%20%20%20%20%20first-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20return%20first%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20second-%3Enext%20%3D%20merge(first%2Csecond-%3Enext)%3B%0A%20%20%20%20%20%20%20%20second-%3Enext-%3Eprev%20%3D%20second%3B%0A%20%20%20%20%20%20%20%20second-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20return%20second%3B%0A%20%20%20%20%7D%0A%7D%0A%0Astruct%20node%20*mergeSort(struct%20node%20*head)%0A%7B%0A%20%20%20%20if%20(!head%20%7C%7C%20!head-%3Enext)%0A%20%20%20%20%20%20%20%20return%20head%3B%0A%20%20%20%20struct%20node%20*second%20%3D%20split(head)%3B%0A%20%0A%0A%20%20%20%20head%20%3D%20mergeSort(head)%3B%0A%20%20%20%20second%20%3D%20mergeSort(second)%3B%0A%20%0A%0A%20%20%20%20return%20merge(head%2Csecond)%3B%0A%7D%0A%20%0A%0Avoid%20insert(struct%20node%20**head%2C%20int%20data)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%0A%20%20%20%20%20%20%20%20(struct%20node%20*)malloc(sizeof(struct%20node))%3B%0A%20%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20%20temp-%3Enext%20%3D%20temp-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20if%20(!(*head))%0A%20%20%20%20%20%20%20%20(*head)%20%3D%20temp%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20temp-%3Enext%20%3D%20*head%3B%0A%20%20%20%20%20%20%20%20(*head)-%3Eprev%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20(*head)%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%0Avoid%20print(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%20%20%20printf(%22Forward%20Traversal%20using%20next%20poitner%5Cn%22)%3B%0A%20%20%20%20while%20(head)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2Chead-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5CnBackward%20Traversal%20using%20prev%20pointer%5Cn%22)%3B%0A%20%20%20%20while%20(temp)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20temp-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Eprev%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%0Avoid%20swap(int%20*A%2C%20int%20*B)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*A%3B%0A%20%20%20%20*A%20%3D%20*B%3B%0A%20%20%20%20*B%20%3D%20temp%3B%0A%7D%0A%20%0A%0Astruct%20node%20*split(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*fast%20%3D%20head%2C*slow%20%3D%20head%3B%0A%20%20%20%20while%20(fast-%3Enext%20%26%26%20fast-%3Enext-%3Enext)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20fast%20%3D%20fast-%3Enext-%3Enext%3B%0A%20%20%20%20%20%20%20%20slow%20%3D%20slow-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20struct%20node%20*temp%20%3D%20slow-%3Enext%3B%0A%20%20%20%20slow-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%0Aint%20main(void)%0A%7B%0A%20%20%20%20struct%20node%20*head%20%3D%20NULL%3B%0A%20%20%20%20insert(%26head%2C5)%3B%0A%20%20%20%20insert(%26head%2C20)%3B%0A%20%20%20%20insert(%26head%2C4)%3B%0A%20%20%20%20insert(%26head%2C3)%3B%0A%20%20%20%20insert(%26head%2C30)%3B%0A%20%20%20%20insert(%26head%2C10)%3B%0A%20%20%20%20head%20%3D%20mergeSort(head)%3B%0A%20%20%20%20printf(%22%5Cn%5CnLinked%20List%20after%20sorting%5Cn%22)%3B%0A%20%20%20%20print(head)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”c” 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.

[ad type=”banner”]