# 21. Merge Two Sorted Lists

## LeetCode [21. Merge Two Sorted Lists](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### 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:**

![](https://3979976701-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWCWmbVhbhatBCAMIGH%2Fuploads%2Fgit-blob-d76079386a5c1b6452ef4e537497356786fe7d1a%2Fimage%20\(18\).png?alt=media)

```
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:**

```go
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:**

```go
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
}
```