0021.md

21. Merge Two Sorted Lists

Level:

Topic:]

Similar Problem:

• 23. Merge k Sorted Lists

Question

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

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

Intuition

• compare two node value until either list is done
• then, connect the unempty list

Code

Time: O(min(n, m))
Space: O(1)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;

    ListNode dummy = new ListNode(0);
    ListNode prev = dummy;
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            prev.next = p1;
            p1 = p1.next;
        } else{
            prev.next = p2;
            p2 = p2.next;
        }
        prev = prev.next;
    }

    prev.next = p1 != null ? p1:p2;
    return dummy.next;
}