Merge Sort for Doubly Linked List

Problem statement

In this problem, we are given a Doubly Linked List (root node) and are asked to sort it using the merge sort algorithm.

For example

Input:

Output:

Problem Statement Understanding

Let’s try to understand this problem with help of example.

In this problem, we will be given a doubly linked list, and we will have to sort the doubly linked list using Merge Sort.

Let’s suppose the given linked list is:

Now using the merge sort we will sort it to obtain the final sorted linked list:

Merge sort is basically a divide and conquer technique in which, we recursively divide the list into two sub-lists at each step till list size is reduced to one and while backtracking from the recursive call, we have two sorted lists which will be merged together by merge() function in linear time.

The above approach is common to both singly-linked lists and doubly-linked lists. The only difference is that we also have to modify the previous pointer while merging the sorted lists. While merging the doubly linked lists, we have to make sure that the previous pointer points to the previously appended node in the merged list.

Now I think from the above example and explanation it is clear what we have to do in the problem as well as what merge sort is.

Now we will look at approach and algorithm, to know how to apply merge sort on a doubly linked list.

Approach and Algorithm

  • Find the middle node.
  • Split the list around the middle node.
  • Recursively call mergeSort on both sub-lists.
  • Merge both sorted sub-lists.

Finding middle node of the list

a) We will maintain a fast pointer and a slow pointer. Initially, both pointers will point to the head of the linked list.
b) Now, we will move the slow pointer by one node and the fast pointer by two nodes at a time.
c) When the fast pointer reaches the end of the list, the slow pointer will point to the middle node. So, we will return slow.

Merging two sorted linked lists

We will use the merge() function to merge the sorted lists. This function accepts two nodes as parameters, list1(node of the first list) and list2(node of the second list).
d) If list1 is null, return list2.
e) If list2 is null, return list1.
f) If list1 is less than list2 append list1 to the resultant list, else append list2.

Dry Run

Let’s try to visualize it (Visualizing Merge Sort):

Code Implementation


public class Prepbytes {
    static class Node {
        int data;
        Node next;
        Node prev;

        Node() {
        };

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

    public static Node sort(Node head) {
        if (head == null) {
            return head;
        }
       if (head.next == null){
            return head;
        }

        head = mergeSort(head);
        return head;
    }

    public static Node mergeSort(Node dnode) {
        if (dnode == null || dnode.next == null) {
            return dnode;
        }

        Node mid = getMidNode(dnode);
        Node next = mid.next;
        mid.next = null;

        Node l1 = mergeSort(dnode);
        Node l2 = mergeSort(next);

        return merge(l1, l2);
    }

    public static Node merge(Node list1, Node list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.data <= list2.data) {
            list1.next = merge(list1.next, list2);
            list1.next.prev = list1;
            list1.prev = null;
            return list1;
        } else {
            list2.next = merge(list1, list2.next);
            list2.next.prev = list2;
            list2.prev = null;
            return list2;
        }
    }

    public static Node getMidNode(Node node) {
        Node slow = node;
        Node fast = node;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(5);
        head.next.next = new Node(4);
        head.next.next.next = new Node(9);
        head.next.next.next.next = new Node(10);
        head.next.next.next.next.next = new Node(6);

        head = sort(head);
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

Output

1 4 5 6 9 10

Time Complexity: O(n*log(n)), where n is the number of nodes in the linked list. The merge sort divides the list into two sub-list and the two sub-lists are merged in linear time.

So, in this blog, we have tried to explain how you can sort a doubly-linked list using the merge sort algorithm. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Remove every Kth node of the Linked list
Next post Python Stack using a Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *