EasyLinked Lists

Merge Two Sorted Lists

linked-listrecursion

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. Return the head of the merged linked list.

Examples

Example 1

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

Output: [1,1,2,3,4,4]

Constraints

•The number of nodes in both lists is in the range [0, 50].
•-100 <= Node.val <= 100

Hints

Hint 1

Use a dummy head node to simplify edge cases at the start of the list.

Solutions

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else                  { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2; // attach remaining
    return dummy.next;
}

Java

Time: O(m+n) · Space: O(1)