Merge Two Sorted Linked Lists

NeetCode: Merge Two Sorted Linked Lists · LeetCode: 21. Merge Two Sorted Linked Lists · Difficulty: Easy

Merge two sorted linked lists into one sorted list made by splicing together the nodes of the two inputs.

Example

Text

Input:  1 -> 2 -> 4   and   1 -> 3 -> 5    Output: 1 -> 1 -> 2 -> 3 -> 4 -> 5

Java linked structures use null and mutable fields, so the list is a chain of ListNode objects, the end is next == null, and the empty list is null. The helper fromArray builds a list from its values and toList copies a list into an ArrayList for printing.

Brute force: collect, sort, rebuild

Java

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

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = list1; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        for (ListNode cur = list2; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        Collections.sort(values);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        ListNode merged = s.mergeTwoLists(fromArray(1, 2, 4), fromArray(1, 3, 5));
        System.out.println(toList(merged));
    }
}

Output

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

This version builds new nodes, so it does not meet the "splice the nodes of the inputs" wording. It is the baseline.

Time: O((m + n) log(m + n)). Space: O(m + n).

Optimal: splice with a tail pointer

Both lists are already sorted, so the smaller head is always the next node of the result. Keep a dummy node in front, and a tail reference to the last node of the result. Repeatedly move the smaller head onto the tail; when one list runs out, attach the remainder of the other. Using <= when comparing the heads keeps equal values in their original order.

Java

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

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.mergeTwoLists(fromArray(1, 2, 4), fromArray(1, 3, 5))));
        System.out.println(toList(s.mergeTwoLists(null, fromArray(7))));
    }
}

Output

[1, 1, 2, 3, 4, 5]
[7]

Time: O(m + n). Space: O(1): nodes are moved, not copied.