21. 合并两个有序链表 #
题目地址 #
解题思路 #
递归解法 #
参考 一看就会，一写就废？详解递归。
递归的核心在于，我只关注我这一层要干什么，返回什么，至于我的下一层（规模减 1），我不管，我就是甩手掌柜。
那么现在我要 merge L1，L2 我需要怎么做❓
- 当一条链表为空时，返回对方，因为如果返回自己，就退出了，返回对方，不管对方是什么，让下级去判断。
- 如果 L1 第一个元素小于 L2 的？那我得把 L1 的这个元素放到最前面，至于后面的那串长啥样，我不管。我只要接过下级员工干完活后给我的包裹，然后把我干的活附上去（令 L1->next = 这个包裹）就行。
- 这个包裹是下级员工干的活，即
merge(L1->next,L2)。
我该返回啥❓
- 现在不管我的下一层干了什么，又返回了什么给我，我只要知道，假设我的工具人们都完成了任务，那我的任务也就完成了，可以返回最终结果了。
- 最终结果就是我一开始接手的 L1 头结点+下级员工给我的大包裹，要一并交上去，这样我的 boss 才能根据我给它的 L1 头节点往下找，检查我完成的工作。
具体实现 #
```go
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) (x *ListNode) {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
if list1.Val <= list2.Val {
list1.Next = mergeTwoLists(list1.Next, list2)
return list1
} else {
list2.Next = mergeTwoLists(list2.Next, list1)
return list2
}
}
func main() {
x := mergeTwoLists(&ListNode{Val: 1, Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 4,
Next: nil,
},
}}, &ListNode{Val: 1, Next: &ListNode{
Val: 3,
Next: &ListNode{
Val: 4,
Next: nil,
},
}})
fmt.Println(x)
}
```
```go
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) (x *ListNode) {
// 方便遍历完成后快速找到头节点
dummy := &ListNode{}
prev := dummy
for list1 != nil && list2 != nil {
if list1.Val >= list2.Val {
prev.Next = list2
list2 = list2.Next
} else {
prev.Next = list1
list1 = list1.Next
}
prev = prev.Next
}
if list1 != nil {
prev.Next = list1
}
if list2 != nil {
prev.Next = list2
}
return dummy.Next
}
func main() {
x := mergeTwoLists(&ListNode{Val: 1, Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 4,
Next: nil,
},
}}, &ListNode{Val: 1, Next: &ListNode{
Val: 3,
Next: &ListNode{
Val: 4,
Next: nil,
},
}})
fmt.Println(x)
}
```