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: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

Solution

Create a dummyHead that occurs before the real head of the merged list. Use two pointers temp1 and temp2 to point to the current numbers in the two lists. Initially temp1 and temp2 point to the two lists’ heads respectively. While both temp1 and temp2 are in the lists, compare the numbers at temp1 and temp2, add the smaller number to the merged list, and move the corresponding pointer one step ahead. If one pointer reaches the end of the list, which is null, then add the numbers of the other pointer to the merged list. Finally, return dummyHead.next.

two pointers

big-o analysis

current = current.next; // now current is the new end node, but still pointing to next node
current.next = null; // @note: key, cut this node from l1 or l2