Merge Two Sorted Linked Lists — Iterative, Recursive & In-Place

package io.thecodeforge.list;

/**
 * Fundamental building block for linked list operations.
 * One value, one pointer. Nothing else.
 */
public class ListNode {
    int value;       // The actual data this node holds
    ListNode next;   // Arrow pointing to the next node (null if this is the last node)

    // Constructor for quickly creating a node with a value
    ListNode(int value) {
        this.value = value;
        this.next = null;  // By default, a new node points to nothing
    }

    // ── Helper: build a linked list from a plain int array ──────────────────
    public static ListNode fromArray(int[] values) {
        if (values == null || values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // ── Helper: print the list so we can verify output ───────────────────────
    public static String toString(ListNode head) {
        StringBuilder result = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) result.append(" → ");
            current = current.next;
        }
        return result.toString();
    }
}

package io.thecodeforge.list;

/**
 * Iterative merge of two sorted linked lists.
 * Production-safe: O(n+m) time, O(1) space, no stack depth risk.
 */
public class MergeSortedListsIterative {

    public static ListNode mergeSortedLists(ListNode headA, ListNode headB) {
        // Dummy node gives us a stable starting point so we never have to
        // special-case 'what if the result list has no nodes yet'.
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;  // 'tail' always points to the last node in our result

        ListNode pointerA = headA;  // Our cursor walking through List A
        ListNode pointerB = headB;  // Our cursor walking through List B

        // Keep going as long as BOTH lists have unprocessed nodes
        while (pointerA != null && pointerB != null) {

            if (pointerA.value <= pointerB.value) {
                // List A's front node is smaller (or equal) — attach it to result
                tail.next = pointerA;
                pointerA = pointerA.next;
            } else {
                // List B's front node is smaller — attach it to result
                tail.next = pointerB;
                pointerB = pointerB.next;
            }

            tail = tail.next;  // CRITICAL: advance tail to the newly attached node
        }

        // At this point one list is exhausted. The other may still have nodes.
        // Since both remaining sub-lists are already sorted, we can attach in bulk.
        if (pointerA != null) {
            tail.next = pointerA;
        } else {
            tail.next = pointerB;
        }

        // dummy.next is the true head of our merged list — skip the sentinel
        return dummy.next;
    }

    public static void main(String[] args) {
        // Build List A: 1 → 3 → 5 → 9
        ListNode listA = ListNode.fromArray(new int[]{1, 3, 5, 9});

        // Build List B: 2 → 4 → 6 → 8
        ListNode listB = ListNode.fromArray(new int[]{2, 4, 6, 8});

        System.out.println("List A:  " + ListNode.toString(listA));
        System.out.println("List B:  " + ListNode.toString(listB));

        ListNode merged = mergeSortedLists(listA, listB);
        System.out.println("Merged:  " + ListNode.toString(merged));

        // Edge case: one list is empty
        ListNode emptyList = null;
        ListNode singleItem = ListNode.fromArray(new int[]{42});
        ListNode mergedEdge = mergeSortedLists(emptyList, singleItem);
        System.out.println("\nEdge case (null + single node): " + ListNode.toString(mergedEdge));

        // Edge case: lists with duplicate values
        ListNode listC = ListNode.fromArray(new int[]{1, 4, 4, 7});
        ListNode listD = ListNode.fromArray(new int[]{2, 4, 5});
        ListNode mergedDupes = mergeSortedLists(listC, listD);
        System.out.println("Duplicates merged: " + ListNode.toString(mergedDupes));
    }
}

package io.thecodeforge.list;

/**
 * Recursive merge of two sorted linked lists.
 * Elegant but carries O(n+m) stack depth — use only on bounded input.
 */
public class MergeSortedListsRecursive {

    private static final int MAX_SAFE_DEPTH = 5000;

    public static ListNode mergeSortedLists(ListNode headA, ListNode headB) {
        return mergeSortedLists(headA, headB, 0);
    }

    /**
     * Overloaded version with depth guard for production safety.
     */
    private static ListNode mergeSortedLists(ListNode headA, ListNode headB, int depth) {
        // Depth guard: fail fast instead of letting the JVM crash
        if (depth > MAX_SAFE_DEPTH) {
            throw new IllegalStateException(
                "Recursion depth exceeded " + MAX_SAFE_DEPTH + ". " +
                "Use iterative merge for large lists.");
        }

        // ── Base cases ─────────────────────────────────────────────────────
        if (headA == null) return headB;
        if (headB == null) return headA;

        // ── Recursive case ─────────────────────────────────────────────────
        if (headA.value <= headB.value) {
            headA.next = mergeSortedLists(headA.next, headB, depth + 1);
            return headA;
        } else {
            headB.next = mergeSortedLists(headA, headB.next, depth + 1);
            return headB;
        }
    }

    public static void main(String[] args) {
        // Same test cases as the iterative ListNode.fromArray(new int[]{1, 3, 5, 9});
        ListNode listB = ListNode.fromArray(new int[]{2, 4, 6, 8});

        System.out.println("List A:  " + ListNode.toString(listA));
        System.out.println("List B:  " + ListNode.toString(listB));

        ListNode merged = mergeSortedLists(listA, listB);
        System.out.println("Merged:  " + ListNode.toString(merged));

        // Demonstrate with one empty list — recursive base case fires immediately
        ListNode result = mergeSortedLists(null, ListNode.fromArray(new int[]{7, 14, 21}));
        System.out.println("\nOne empty list: " + ListNode.toString(result));

        // Both lists empty — returns null, which represents an empty list
        ListNode bothEmpty = mergeSortedLists version — results must be identical
        ListNode listA =(null, null);
        System.out.println("Both empty: " + (bothEmpty == null ? "(empty list)" : ListNode.toString(bothEmpty)));
    }
}

package io.thecodeforge.list;

/**
 * Merge Sort on a linked list — demonstrates why merge is a fundamental primitive.
 * O(n log n) time, O(1) extra space (unique advantage over array-based merge sort).
 */
public class MergeSortLinkedList {

    // ── Entry point: sort the entire linked list ─────────────────────────────
    public static ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;

        // Split at midpoint
        ListNode midpoint = findMidpoint(head);
        ListNode secondHalfHead = midpoint.next;
        midpoint.next = null;

        // Recursively sort each half
        ListNode sortedFirstHalf = mergeSort(head);
        ListNode sortedSecondHalf = mergeSort(secondHalfHead);

        // Merge the two sorted halves
        return MergeSortedListsIterative.mergeSortedLists(sortedFirstHalf, sortedSecondHalf);
    }

    private static ListNode findMidpoint(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode unsortedList = ListNode.fromArray(new int[]{8, 3, 1, 6, 2, 9, 4, 7, 5});
        System.out.println("Before sort: " + ListNode.toString(unsortedList));

        ListNode sortedList = mergeSort(unsortedList);
        System.out.println("After sort:  " + ListNode.toString(sortedList));

        // Simulate merging two ordered event logs by timestamp
        ListNode serverOneLog = ListNode.fromArray(new int[]{101, 204, 307, 502});
        ListNode serverTwoLog = ListNode.fromArray(new int[]{150, 255, 410, 490, 610});
        System.out.println("\nServer 1 log: " + ListNode.toString(serverOneLog));
        System.out.println("Server 2 log: " + ListNode.toString(serverTwoLog));
        ListNode unifiedLog = MergeSortedListsIterative.mergeSortedLists(serverOneLog, serverTwoLog);
        System.out.println("Unified log:  " + ListNode.toString(unifiedLog));
    }
}