21. Merge Two Sorted Lists

LeetCode 21. Merge Two Sorted Lists

Description

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both l1 and l2 are sorted in non-decreasing order.

Tags

Linked List, Recursion

Solution

Solution 1 - Iteration:

We initialize a dummy head first and assign a pointer to it. We first enter a loop with the condition that both pointers on l1 and l2 are not null. In the loop, the node with smaller value will be connected to the next of the pointer on the new list. After the loop, we concatenate the non-empty list onto the tail of the new list. Finally, return the next node of the dummy head.

Solution 2 - Recursion:

If one of the pointers on certain input list is null, we return the other pointer. If both pointers are not null, we obtain the merge result of the node with larger value and the next of the other node, and assign it to the node with smaller value's next, and return this smaller node.

Complexity

• Time complexity: $O(n)$, n for the length of the longer list；

• Space complexity: $O(m+n)$, created a new list as the result.

Code

Solution 1:

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	res := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			head.Next = l1
			l1 = l1.Next
		} else {
			head.Next = l2
			l2 = l2.Next
		}
		head = head.Next
		head.Next = nil
	}
	if l1 != nil {
		head.Next = l1
	}
	if l2 != nil {
		head.Next = l2
	}
	return res.Next
}

Solution 2:

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists(l1, l2.Next)
	return l2
}