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