> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/21.-merge-two-sorted-lists.md).

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

![](/files/RDEOXx2gPcdDBNbAJVwN)

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/21.-merge-two-sorted-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.