Linked List: Program to merge two sorted linked list

Write a program to merge two sorted linked list

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list.

For merging two linked list we take two pointers and point them on head nodes of respective linked lists.
After comparing the data of both of pointer nodes, we pick the smaller element and make that node as the new head of our merged linked list
Then we increment the pointer to the next element and do the comparison again. We keep repeating this step
until all the elements of both linked list have been checked and added to the new merged linked list.

Algorithm

1. Pass the head pointers of the two linked lists to the mergeTwoSortedLL function
2. Create two temporary pointers that point to these heads as temp1 and temp2
3. Create a new third pointer called 'sortTemp' that will point to the smaller of temp1 and temp2
4. Initialize the head of the new merged linked list to this pointer sortTemp
5. While temp1 and temp2 are not null
   • If temp1.data is less than temp2.data
     • sortTemp.next = temp1
     • sortTemp = temp1
     • temp1 = sortTemp.next
   • Else
     • sortTemp.next = temp2;
     • sortTemp = temp2;
     • temp2 = sortTemp.next;
6. Now point the sortTemp to the linked list that still has elements left if any

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

Java Code

 import java.util.*;

 class MergeLinkedList{
        class Node {
            // initialising data field and next pointer of node
            int data;
            Node next;
         
            Node(int d) {
                data = d;
            }
        }
    
        Node head;
    
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = this.head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
    
    
        public void buildLinkedlist(int arrayElements[]) {
            int i;
            int noOfNodes = arrayElements.length;
            Node temp, last;
            temp = new Node(arrayElements[0]);
            temp.next = null;
            this.head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(arrayElements[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
    
        public void mergeTwoSortedLL(Node head1, Node head2){
    
            Node temp1 = head1;
            Node temp2 = head2;
            Node sortTemp = temp1.data < temp2.data ? temp1 : temp2;
    
            this.head = sortTemp;
    
            if(sortTemp == temp1){
                temp1 = sortTemp.next;
            }
            if(sortTemp == temp2){
                temp2 = sortTemp.next;
            }
    
            while(temp1 != null && temp2 != null){
    
                if(temp1.data < temp2.data){
                    sortTemp.next = temp1;
                    sortTemp = temp1;
                    temp1 = sortTemp.next;
                }else{
                    sortTemp.next = temp2;
                    sortTemp = temp2;
                    temp2 = sortTemp.next;
                }
            }
    
            if(temp1 == null){
                sortTemp.next = temp2;
            }
            if(temp2 == null){
                sortTemp.next = temp1;
            }
    
    
        }
    
        public static void main(String[] args) {
            int[] linkedlistElements1 = new int[] { 1, 3, 7, 9, 11 };
            int[] linkedlistElements2 = new int[] { 2, 4, 5 };
    
            // initialising object of linkedlist class
            MergeLinkedList ll1 = new MergeLinkedList();
            MergeLinkedList ll2 = new MergeLinkedList();
            MergeLinkedList ll3 = new MergeLinkedList();
    
            ll1.buildLinkedlist(linkedlistElements1);
            System.out.println("First Sorted Linked List ");
            ll1.printLinkedlist();
    
            ll2.buildLinkedlist(linkedlistElements2);
            System.out.println("Second Sorted Linked List ");
            ll2.printLinkedlist();
    
            ll3.mergeTwoSortedLL(ll1.head, ll2.head);
            System.out.println("After Merging Above Sorted linkedlist Elements");
            ll3.printLinkedlist();
     
        }
    
 }

Output

First Sorted Linked List
1 -> 3 -> 7 -> 9 -> 11
Second Sorted Linked List
2 -> 4 -> 5
After Merging Above Sorted linkedlist Elements
1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 9 -> 11