Merge Two Sorted Linked Lists

Given the heads of two sorted linked lists, merge them into one sorted list made by splicing together the nodes of the two lists, and return its head.

LeetCode: 21. Merge Two Sorted Lists

Example

Text

Input:  1 -> 2 -> 4,  1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Brute force: collect and sort

A Java list node is an object with a mutable next field. null marks the end of the list, so an empty list is null and no wrapper type is needed.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> values = new ArrayList<>();
        for (ListNode n = l1; n != null; n = n.next) values.add(n.val);
        for (ListNode n = l2; n != null; n = n.next) values.add(n.val);
        Collections.sort(values);
        ListNode head = null;
        for (int i = values.size() - 1; i >= 0; i--) {
            head = new ListNode(values.get(i), head);
        }
        return head;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(mergeTwoLists(fromArray(1, 2, 4), fromArray(1, 3, 4))));
    }
}

Output

[1, 1, 2, 3, 4, 4]

Time: O((m + n) log(m + n)). Space: O(m + n). It ignores that the inputs are sorted, and it allocates new nodes.

Optimal: splice the nodes

Compare the two heads, detach the smaller one from its list, and append it to the result. A dummy node placed before the result gives tail a node to attach to, so the first append needs no special case. When one list runs out, the rest of the other is already sorted and is attached in one step.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(mergeTwoLists(fromArray(1, 2, 4), fromArray(1, 3, 4))));
        System.out.println(show(mergeTwoLists(fromArray(), fromArray(0))));
        System.out.println(show(mergeTwoLists(fromArray(5, 6), fromArray(1, 2, 3))));
    }
}

Output

[1, 1, 2, 3, 4, 4]
[0]
[1, 2, 3, 5, 6]

Time: O(m + n). Space: O(1): the existing nodes are reused. The merged list shares nodes with the inputs, so the input lists must not be used after the merge.

Edge cases

One or both lists empty: the loop does not run, and tail.next receives whichever list is not null (or null when both are empty).
Equal values: <= takes from l1 first, which keeps the merge stable.