Merge K Sorted Lists

Merge Two Sorted Lists (LC.21)

Merge two sorted linked lists and return it as a new list.

The new list should be made by splicing together the nodes of the first two lists.

Example

Input: L1 = 1->3->8->11->15->null, L2 = 2->null
Return: 1->2->3->8->11->15->null

Analysis

It should be similar to merge two sort arrays. So we merge two lists until one list is exhausted. Then splice the results with leftovers in either L1 or L2.

Code

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;
    ListNode result = new ListNode(0), rp = result;
    // merge them until one list is exhausted
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            rp.next = p1;
            rp = rp.next;
            p1 = p1.next;
        } else {
            rp.next = p2;
            rp = rp.next;
            p2 = p2.next;
        }
    }
    // if L1 has leftover nodes
    if (p1 != null) {
        rp.next = p1;
    }
    // else if L2 has leftover nodes
    if (p2 != null) {
        rp.next = p2;
    }
    return result.next;
}

Merge K Sorted Lists (LC.23)

Merge k sorted linked lists and return it as one sorted list.

Example

Analysis