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 (DLL):

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
Doubly Linked List

Doubly Linked List

JAVA Programming Implementation of merge sort for doubly linked list:

Java


class LinkedList {

static Node head;


static class Node {

int data;
Node next, prev;


Node(int d) {
data = d;
next = prev = null;
}
}

void print(Node node) {
Node temp = node;
System.out.println("Forward Traversal using next pointer");
while (node != null) {
System.out.print(node.data + " ");
temp = node;
node = node.next;
}
System.out.println("\nBackward Traversal using prev pointer");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.prev;
}
}


Node split(Node head) {
Node fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
Node temp = slow.next;
slow.next = null;
return temp;
}

Node mergeSort(Node node) {
if (node == null || node.next == null) {
return node;
}
Node second = split(node);


node = mergeSort(node);
second = mergeSort(second);


return merge(node, second);
}


Node merge(Node first, Node second) {

if (first == null) {
return second;
}


if (second == null) {
return first;
}


if (first.data < second.data) {
first.next = merge(first.next, second);
first.next.prev = first;
first.prev = null;
return first;
} else {
second.next = merge(first, second.next);
second.next.prev = second;
second.prev = null;
return second;
}
}


public static void main(String[] args) {

LinkedList list = new LinkedList();
list.head = new Node(10);
list.head.next = new Node(30);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(20);
list.head.next.next.next.next.next = new Node(5);


Node node = null;
node = list.mergeSort(head);
System.out.println("Linked list after sorting :");
list.print(node);

}
}

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”]