Leetcode: Merge Two Sorted Lists

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.

Understanding the problem:

The question has for merging two sorted linked lists and return it as a new list. Note that the question requires the in-place transform, which means that we are not allowed to create a new merged linked list. 

Several examples to illustrate the question:

1  ->  3  ->  5  ->  7

2  ->  4  ->  6  ->  8

The merged list is 1  ->  2  -> 3  -> 4  -> 5  -> 6  -> 7  -> 8

1  ->  2  -> 3   -> 4

5  -> 6   -> 7   -> 8

The merged list is 1 -> 2  -> 3  -> 4  -> 5  -> 6   ->  7  ->  8

Naive Solution:

If you remember the question of merging two sorted array, this question is very closed to that one. The basic idea is to use two pointers pointing to the two linked list. The crux is to define a new fake head. Compare the first element from each list, merge the smaller one into the merged list. At last, when one list is empty, append the rest of the other one into the merged list.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // handle null linked lists
        if (l1 == null) return l2;
        else if (l2 == null) return l1;
        
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode newHead = new ListNode(0);
        ListNode p = newHead;
        
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        
        if (p1 != null) {
            p.next = p1;
        } else if (p2 != null) {
            p.next = p2;
        }
        
        return newHead.next;
    }
}

Discussion:
The solution takes O(n + m) in time, since we traverse the linked lists only once. The space complexity is O(1). 

Summary:
Note the idea of using the fake head. It is much trickier than merging two sorted arrays. If the question requires the in-place merge, we must think about using the fake head.