Merge two sorted linked lists into a single sorted linked list while maintaining the sorted order of the elements.

Approach: The solution uses two pointers to traverse both linked lists simultaneously. At each step, the smaller node is selected and added to the merged list, and the corresponding pointer is moved forward. Once one of the lists is exhausted, the remaining nodes from the other list are appended to the result.

A dummy node is used to simplify list construction and avoid handling special cases for the head node separately.

Java Solution:

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
    }
}

public class MergeSortedLists {

    public static ListNode mergeLists(ListNode firstList, ListNode secondList) {
        ListNode dummyNode = new ListNode(-1);
        ListNode current = dummyNode;

        while (firstList != null && secondList != null) {
            if (firstList.value <= secondList.value) {
                current.next = firstList;
                firstList = firstList.next;
            } else {
                current.next = secondList;
                secondList = secondList.next;
            }

            current = current.next;
        }

        if (firstList != null) {
            current.next = firstList;
        }

        if (secondList != null) {
            current.next = secondList;
        }

        return dummyNode.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.value + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode firstList = new ListNode(1);
        firstList.next = new ListNode(3);
        firstList.next.next = new ListNode(5);

        ListNode secondList = new ListNode(2);
        secondList.next = new ListNode(4);
        secondList.next.next = new ListNode(6);

        ListNode mergedList = mergeLists(firstList, secondList);

        printList(mergedList);
    }
}

Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. Each node is visited exactly once.

Space Complexity: O(1), as the merge operation reuses the existing nodes without allocating additional storage proportional to the input size.

Key Interview Points: • The two-pointer technique is the standard and most efficient approach for merging sorted linked lists. • Using a dummy node simplifies the implementation by eliminating special handling for the head node. • This problem forms the foundation for the Merge Sort algorithm on linked lists and is frequently asked in coding interviews.