1. Introduction

Merging two sorted linked lists into one sorted linked list is a common problem in computer science. This operation is fundamental in algorithms like the merge sort. Given two sorted linked lists, we aim to merge them in a sorted manner to get a single sorted linked list without using any extra space.

2. Program Steps

1. Initialize a new node, mergedHead, to serve as the starting node of the merged linked list.

2. Compare the heads of the two linked lists.

3. Append the node with the smaller value to mergedHead and move to the next node in that list.

4. Repeat until one of the lists is empty.

5. Append the remaining nodes from the non-empty list to mergedHead.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

public class MergeSortedLists {

    Node sortedMerge(Node list1, Node list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.data < list2.data) {
            list1.next = sortedMerge(list1.next, list2);
            return list1;
        } else {
            list2.next = sortedMerge(list1, list2.next);
            return list2;
        }
    }

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

    public static void main(String[] args) {
        MergeSortedLists list = new MergeSortedLists();

        Node list1 = new Node(1);
        list1.next = new Node(3);
        list1.next.next = new Node(5);

        Node list2 = new Node(2);
        list2.next = new Node(4);
        list2.next.next = new Node(6);

        Node mergedList = list.sortedMerge(list1, list2);
        list.printList(mergedList);
    }
}

Output:

1 2 3 4 5 6

4. Step By Step Explanation

1. We define a Node class to represent each node in our linked list, containing data and a reference to the next node.

2. The sortedMerge function recursively compares the data values of the nodes in two linked lists and merges them into a single sorted linked list.

3. If one of the lists is empty, it returns the other list as they are already sorted.

4. If list1's current node has a value less than list2's current node, we move to the next node in list1. Otherwise, we move to the next node in list2.

5. The merged nodes are connected using recursive calls to sortedMerge.

6. The printList function is used to display our merged list.