Merge Two Sorted Linked Lists

This post talks about, merging two sorted linked lists into one sorted linked list. The implementation doesn't use any extra space(except head node overhead). It's implemented below in Java, but same approach can be applied in any programming language.

Merge method takes two sorted linked lists as arguments and returns the head of the final merged linked list.

First Linked List       1 -->6 -->13 -->49 -->114 -->null

Second Linked List   5 -->9 -->23 -->null

Merged Linked List  1 -->5 -->6 -->9 -->13 -->23 -->49 -->114 -->null

The merge method uses a new node i.e. merged to generate the merged list. It starts with the smallest node of either list and keeps on adding the next larger node (in while loop). Method will come out of the while loop if either of the lists is traveled fully. Then the remaining nodes of other list get appended to the end of merged list.

 package algo;  
   
 /**  
  * LinkedList implementation which merges two sorted linkedlists without using  
  * any extra space (except overhead of head)  
  *   
  * @author Siddheshwar  
  *   
  */  
 public class MergeLinkedList<E extends Comparable<E>> {  
      Node<E> head;  
   
      /**  
       * merges two sorted linked lists and returns node of the merged list  
       *   
       */  
      public Node<E> merge(Node<E> n1, Node<E> n2) {  
           Node<E> merged = null; // pointer for merged list  
           Node<E> resp = null; // head of merged list  
   
           if (n1 == null)  
                return n2;  
           if (n2 == null)  
                return n1;  
   
           int cmp = 0;  
           while (n1 != null && n2 != null) {  
                cmp = n1.compareTo(n2);  
                if (merged == null) {  
                     if (cmp < 0) {  
                          merged = n1;  
                          n1 = n1.next;  
                     } else {  
                          merged = n2;  
                          n2 = n2.next;  
                     }  
                     resp = merged; // points to head of merged list  
                } else {  
                     if (cmp < 0) {  
                          merged.next = n1;  
                          n1 = n1.next;  
                          merged = merged.next;  
                     } else {  
                          merged.next = n2;  
                          n2 = n2.next;  
                          merged = merged.next;  
                     }  
                }  
           }  
   
           // append the remaining nodes of the either list  
           if (n1 == null)  
                merged.next = n2;  
           else  
                merged.next = n1;  
   
           return resp;  
      }  
   
      /**  
       * Node implementation which forms linked list  
       *   
       */  
      private static class Node<E extends Comparable<E>> implements  
                Comparable<Node<E>> {  
           E data;  
           Node<E> next;  
   
           public Node(E data, Node<E> next) {  
                super();  
                this.data = data;  
                this.next = next;  
           }  
   
           @Override  
           public String toString() {  
                return "Node [data=" + data + "]";  
           }  
   
           @Override  
           public int compareTo(Node<E> node) {  
                return this.data.compareTo(node.data);  
           }  
      }  
   
      public void addNodeLast(E d) {  
           if (head == null) {  
                head = new Node<E>(d, null);  
                return;  
           }  
           Node<E> h = head;  
           while (h.next != null)  
                h = h.next;  
           h.next = new Node<E>(d, null);  
      }  
   
      public void print() {  
           Node<E> h = head;  
           while (h != null) {  
                System.out.print(h.data + " -->");  
                h = h.next;  
           }  
           System.out.println("null");  
      }  
   
      public void print(Node<E> head) {  
           Node<E> h = head;  
           while (h != null) {  
                System.out.print(h.data + " -->");  
                h = h.next;  
           }  
           System.out.println("null");  
      }  
   
      /**  
       * Main method for testing  
       */  
      public static void main(String[] args) {  
           /**  
            * First linked list  
            */  
           MergeLinkedList<Integer> l1 = new MergeLinkedList<>();  
           l1.addNodeLast(1);  
           l1.addNodeLast(6);  
           l1.addNodeLast(13);  
           l1.addNodeLast(49);  
           l1.addNodeLast(114);  
           System.out.print("First Linked List :");  
           l1.print(l1.head);  
   
           /**  
            * Second linked list  
            */  
           MergeLinkedList<Integer> l2 = new MergeLinkedList<>();  
           l2.addNodeLast(5);  
           l2.addNodeLast(9);  
           l2.addNodeLast(23);  
           System.out.print("Second Linked List :");  
           l2.print(l2.head);  
   
           /**  
            * Final, merged linked list  
            */  
           MergeLinkedList<Integer> mergedList = new MergeLinkedList<>();  
           mergedList.head = mergedList.merge(l1.head, l2.head);  
           System.out.print("Merged Linked List :");  
           mergedList.print(mergedList.head);  
      }  
 }  
   

I have implemented it in Java using Generics so that you can store any type of object in the node. One of the tricky aspects is the implementation of the Comparable interface. 

Note that compareTo(..) method in the Node class basically compares the data stored in the node. And it assumes that the data is comparable. This will be perfectly fine as long as you are using inbuilt classes like String, Integer as they implement Comparable. But if you need to compare your own custom object (say Student, Animal), make sure that the class implements the Comparable interface.