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

21. 合并两个有序链表 #

题目地址 #

解题思路 #

递归解法 #

具体实现 #

参考 #