Write a program to implement Merge sort using linked list

Merge sort is a comparison-based sorting algorithm. It uses divide and conquer logic to sort the items. Linked list is a data structure. Each record of a linked list is called as the node. The field of each node that contains the address of the next node.

Write a program to implement Merge sort using linked list.

Algorithm Explanation

	If linked list has only one element, no need sort the linked list.
	Otherwise, divide the linked list into two halves. Sort recursively using divide and conquer strategy.
	After sorting, merge two list into one single list which contain sorted elements in linked list.
	Return the sorted linked list and print the elements.

Source Code

package com.dsacode.DataStructre.linkedlist;
 
class ListNode {
    public  int val;
    public ListNode next;
  
    public ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class MergesortLinkList {
 
        public static ListNode mergeSortList(ListNode head) {
      
            if (head == null || head.next == null)
                return head;
      
            int count = 0;
            ListNode p = head;
            while (p != null) {
                count++;
                p = p.next;
            }
      
            int middle = count / 2;
      
            ListNode l = head, r = null;
            ListNode p2 = head;
            int countHalf = 0;
            while (p2 != null) {
                countHalf++;
                ListNode next = p2.next;
      
                if (countHalf == middle) {
                    p2.next = null;
                    r = next;
                }
                p2 = next;
            }
      
            ListNode h1 = mergeSortList(l);
            ListNode h2 = mergeSortList(r);
      
            ListNode merged = merge(h1, h2);
      
            return merged;
        }
      
        public static ListNode merge(ListNode l, ListNode r) {
            ListNode p1 = l;
            ListNode p2 = r;
      
            ListNode fakeHead = new ListNode(100);
            ListNode pNew = fakeHead;
      
            while (p1 != null || p2 != null) {
      
                if (p1 == null) {
                    pNew.next = new ListNode(p2.val);
                    p2 = p2.next;
                    pNew = pNew.next;
                } else if (p2 == null) {
                    pNew.next = new ListNode(p1.val);
                    p1 = p1.next;
                    pNew = pNew.next;
                } else {
                    if (p1.val < p2.val) {
                        pNew.next = new ListNode(p1.val);
                        p1 = p1.next;
                        pNew = pNew.next;
                    } else if (p1.val == p2.val) {
                        pNew.next = new ListNode(p1.val);
                        pNew.next.next = new ListNode(p1.val);
                        pNew = pNew.next.next;
                        p1 = p1.next;
                        p2 = p2.next;
      
                    } else {
                        pNew.next = new ListNode(p2.val);
                        p2 = p2.next;
                        pNew = pNew.next;
                    }
                }
            }
      
            return fakeHead.next;
        }
      
        public static void main(String[] args) {
            System.out.println("Insert items  in LinkedList:9");
            ListNode n1 = new ListNode(9);
            System.out.println("Insert items  in LinkedList:43");
            ListNode n2 = new ListNode(43);
            System.out.println("Insert items  in LinkedList:34");
            ListNode n3 = new ListNode(34);
      
            System.out.println("Insert items  in LinkedList:11");
            ListNode n4 = new ListNode(11);
             
            System.out.println("Insert items  in LinkedList:78");
            ListNode n5 = new ListNode(78);
             
            System.out.println("Insert items  in LinkedList:55");
            ListNode n6 = new ListNode(55);
      
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
            n5.next = n6;
            System.out.print("Sort items  in LinkedList:");
            n1 = mergeSortList(n1);
      
            printList(n1);
        }
      
        public static void printList(ListNode x) {
            if(x != null){
                System.out.print(x.val + "->");
                while (x.next != null) {
                    System.out.print(x.next.val + "->");
                    x = x.next;
                }
                System.out.println("NULL");
            }
      
        }
 
}

Output

Insert items in LinkedList:9
Insert items in LinkedList:43
Insert items in LinkedList:34
Insert items in LinkedList:11
Insert items in LinkedList:78
Insert items in LinkedList:55
Sort items in LinkedList:9->11->34->43->55->78->NULL