Given two singly-linked lists that are already sorted in ascending order, produce a single sorted linked list that interleaves all node from both input lists.

Examples

• Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
  Output: [1, 1, 2, 3, 4, 4]
• Input: list1 = [], list2 = []
  Output: []
• Input: list1 = [], list2 = [0]
  Output: [0]

Implementation strategies

1. Top-down recursion Compare the heads of list1 and list2. Whichveer node holds the smaller value becomes the head of the merged result, and its next pointer is assigned the result of recursively merging the remainder of that list with the other list. The recursion bottoms out when either list becomes null.

2. Iterative copying Initialize a dummy root node and a trailing pointer. Walk through the two lists with separate pointers; at each step, create a brand-new node whose value equals the smaller candidate, attach it, and advance the corresponding pointer. Once one list is exhausted, append the remaining nodes from the other list.

3. In‑place pointer weaving Create a dummy pre-head node. Maintain a prev reference that tracks the last node appended. Iterate with two pointers a and b traversing the original lists. In each iteration, attach the smaller node to prev.next, advance the consumed pointer, then move prev forward. After the loop, link the non-null remainder. Return dummy.next as the final head.

Node definition (Java)

static class Node {
    int data;
    Node next;

    Node() {}

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

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

Recursive implementation

public Node combineRecursive(Node a, Node b) {
    if (a == null) return b;
    if (b == null) return a;

    if (a.data < b.data) {
        a.next = combineRecursive(a.next, b);
        return a;
    } else {
        b.next = combineRecursive(a, b.next);
        return b;
    }
}

Iterative copy approach

public Node combineByCopying(Node a, Node b) {
    if (a == null) return b;
    if (b == null) return a;

    Node pointerA = a;
    Node pointerB = b;
    Node resultHead = null;
    Node resultTail = null;

    while (pointerA != null && pointerB != null) {
        int chosenValue;
        if (pointerA.data <= pointerB.data) {
            chosenValue = pointerA.data;
            pointerA = pointerA.next;
        } else {
            chosenValue = pointerB.data;
            pointerB = pointerB.next;
        }

        Node freshNode = new Node(chosenValue, null);
        if (resultHead == null) {
            resultHead = resultTail = freshNode;
        } else {
            resultTail.next = freshNode;
            resultTail = freshNode;
        }
    }

    if (pointerA != null) resultTail.next = pointerA;
    if (pointerB != null) resultTail.next = pointerB;

    return resultHead;
}

In‑place iterative merge

public Node combineInPlace(Node first, Node second) {
    if (first == null) return second;
    if (second == null) return first;

    Node dummy = new Node(-1);
    Node prev = dummy;
    Node cursor1 = first;
    Node cursor2 = second;

    while (cursor1 != null && cursor2 != null) {
        if (cursor1.data <= cursor2.data) {
            prev.next = cursor1;
            cursor1 = cursor1.next;
        } else {
            prev.next = cursor2;
            cursor2 = cursor2.next;
        }
        prev = prev.next;
    }

    prev.next = (cursor1 != null) ? cursor1 : cursor2;

    return dummy.next;
}