Formatted question description: https://leetcode.ca/all/21.html

21. Merge Two Sorted Lists

Level

Easy

Description

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

Code

public class Merge_Two_Sorted_Lists {

	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; }
	 * }
	 */

	// Time complexity : O(N)
	public class Solution {
	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

	        ListNode dummy = new ListNode(0);
	        ListNode current = dummy;

	        while (l1 != null || l2 != null) {
	            int v1 = (l1 == null? Integer.MAX_VALUE : l1.val);
	            int v2 = (l2 == null? Integer.MAX_VALUE : l2.val);

	            if (v1 < v2) {
	                current.next = l1;
	                l1 = l1.next;
	            } else {
	                current.next = l2;
	                l2 = l2.next;
	            }

	            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
	        }

	        return dummy.next;
	    }
	}

	public class Solution_extraSpace {
	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

	        ListNode dummy = new ListNode(0);
	        ListNode current = dummy;

	        while (l1 != null || l2 != null) {
	            int v1 = l1 == null ? Integer.MAX_VALUE : l1.val;
	            int v2 = l2 == null ? Integer.MAX_VALUE : l2.val;

	            if (v1 < v2) {
	                current.next = new ListNode(v1); // requires extra o(N) space
	                l1 = l1.next;
	            }
	            else {
	                current.next = new ListNode(v2);
	                l2 = l2.next;
	            }

	            current = current.next;
	        }

	        return dummy.next;
	    }
	}
}