In this problem we are given two sorted linked lists and asked to merge the two in such a way that the final output should be a sorted list containing all the elements from both the lists.

Solution

We can solve this problem using the same approach as we do in merge sort. Below is the algorithm to approach this

1. Have two pointers, FIRST and SECOND which points to the head node of the first list and the second respectively.
2. Have two more pointers, HEAD which will be storing the reference of the first node of the merged list and CURRENT which will point to the latest node added to the new merged list.
3. Repeat until either FIRST or SECOND becomes null i.e., until we reach the end of either of lists.
   1. If data at FIRST is smaller or equal to data at SECOND then
      1. Add the node pointed by FIRST at the beginning or after the node pointed by CURRENT.
      2. Set CURRENT to FIRST.
      3. Move FIRST to the next node.
   2. Else,
      1. Add the node pointed by SECOND at the beginning or after the node pointed by CURRENT.
      2. Set CURRENT to SECOND.
      3. Move SECOND to the next node
4. If the first list is not completely traversed then add all its elements to the new merged list.
5. If the second list is not completely traversed then add all its elements in the new merged list.
6. Return HEAD of the new merged list.

Below is the implementation of the above algorithm in Java.

    private static Node mergeLists(Node listHead1, Node listHead2) {
        Node first = listHead1;
        Node second = listHead2;
        Node head = null;
        Node current = null;

        while (first != null && second != null) {
            if (first.data <= second.data) {
                if (head == null) {
                    head = first;
                } else {
                    current.next = first;
                }

                current = first;
                first = first.next;
            } else {
                if (head == null) {
                    head = second;
                } else {
                    current.next = second;
                }

                current = second;
                second = second.next;
            }
        }

        while (first != null) {
            current.next = first;
            current = first;
            first = first.next;
        }

        while (second != null) {
            current.next = second;
            current = second;
            second = second.next;
        }

        return head;
    }

Complete working program

Below is the complete working program to test the solution is given below.

package com.theaconitedev;

public class Main {

    private static class Node {
        private int data;
        private Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        Node listHead1 = getNewList(1, 2, 6);
        System.out.print("List 1: ");
        printList(listHead1);

        Node listHead2 = getNewList(2, 2, 6);
        System.out.print("List 1: ");
        printList(listHead2);

        Node mergedList = mergeLists(listHead1, listHead2);
        System.out.print("Merged list: ");
        printList(mergedList);
    }

    private static Node getNewList(int start, int incrementBy, int numberOfNodes) {
        Node head = null;
        Node current = null;

        for (int i = start, count = 1; count <= numberOfNodes; count++, i += incrementBy) {
            Node node = new Node(i);

            if (head == null) {
                head = node;
            } else {
                current.next = node;
            }

            current = node;
        }

        return head;
    }

    private static void printList(Node current) {
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    private static Node mergeLists(Node listHead1, Node listHead2) {
        Node first = listHead1;
        Node second = listHead2;
        Node head = null;
        Node current = null;

        while (first != null && second != null) {
            if (first.data <= second.data) {
                if (head == null) {
                    head = first;
                } else {
                    current.next = first;
                }

                current = first;
                first = first.next;
            } else {
                if (head == null) {
                    head = second;
                } else {
                    current.next = second;
                }

                current = second;
                second = second.next;
            }
        }

        while (first != null) {
            current.next = first;
            current = first;
            first = first.next;
        }

        while (second != null) {
            current.next = second;
            current = second;
            second = second.next;
        }

        return head;
    }
}

List 1: 1 3 5 7 9 11 
List 1: 2 4 6 8 10 12 
Merged list: 1 2 3 4 5 6 7 8 9 10 11 12