需求
將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。
新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的铜邮。
示例：
輸入：1->3->5->7->9, 0->2->4->6->8
輸出：0->1->2->3->4->5->6->7->8->9
思路
抓住需求的關(guān)鍵信息——"兩個(gè)升序鏈表"
說明兩個(gè)鏈表都是有序的昔搂，也就是將兩個(gè)有序的鏈表重新合并成一個(gè)整體有序的鏈表树叽。
思路就是挨個(gè)比較兩個(gè)鏈表中的元素阿弃，誰更小就先取誰，然后記得將指針移到下一個(gè)節(jié)點(diǎn)缀雳，直到遍歷完兩個(gè)鏈表渡嚣。
具體步驟如下
1、數(shù)據(jù)初始化
最終要返回一個(gè)有序的合并后的鏈表肥印，就需要先初始化一個(gè)結(jié)果鏈表识椰，即result。
2深碱、遍歷兩個(gè)鏈表腹鹉，比較大小
顯然l1.Val=0 < l2.Val=1，所以將l1.Val賦值給結(jié)果鏈表敷硅。
這里有一個(gè)問題：如果直接使用result功咒，第一個(gè)元素指向l1.Val后，需要移動到下一個(gè)節(jié)點(diǎn)來保存下一個(gè)節(jié)點(diǎn)值绞蹦，那這個(gè)result指針就是一直在變力奋，直到兩個(gè)鏈表遍歷完成。這時(shí)候返回的result就不在是一個(gè)完整的鏈表幽七，而是指向最后一個(gè)節(jié)點(diǎn)的指針景殷。
所以，我們還需要一個(gè)新的指針，用于標(biāo)識指向新節(jié)點(diǎn)的位置滨彻。
3、聲明當(dāng)前位置指針
將節(jié)點(diǎn)賦值給cur指針挪蹭，同時(shí)cur指針移動到下一個(gè)節(jié)點(diǎn)
4亭饵、重復(fù)已上，遍歷完兩個(gè)鏈表
此時(shí)cur指針指向節(jié)點(diǎn)9梁厉。l1和l2都指向尾結(jié)點(diǎn)辜羊。
代碼如下
package main
import "fmt"
/**
兩個(gè)有序的鏈表合并
*/
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) (result *ListNode) {
if l1 == nil && l2 == nil {
return nil
}
result = &ListNode{}
cur := result
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = &ListNode{Val: l1.Val}
l1 = l1.Next
} else {
cur.Next = &ListNode{Val: l2.Val}
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return result.Next // 這里將初始化的頭結(jié)點(diǎn)過濾掉
}
func initLinkList() *ListNode {
head := &ListNode03{Val: 0}
ln := head
for i := 2; i < 10; i = i + 2 {
tmp := &ListNode{Val: i}
head.Next = tmp
head = head.Next
}
return ln
}
func initLinkList2() *ListNode {
head := &ListNode{Val: 1}
ln := head
for i := 3; i < 10; i = i + 2 {
tmp := &ListNode{Val: i}
head.Next = tmp
head = head.Next
}
return ln
}
func main() {
l1 := initLinkList()
l2 := initLinkList2()
result := mergeTwoLists(l1, l2)
for result != nil {
fmt.Print(result.Val, " ")
result = result.Next
}
}
注意
- 如果其中一個(gè)鏈表已經(jīng)遍歷完，另一個(gè)鏈表還有未遍歷完的元素词顾，則將未遍歷部分直接賦值給cur
- mergeTwoLists方法返回的時(shí)候需要過濾掉頭結(jié)點(diǎn)八秃，因?yàn)槌跏蓟臅r(shí)候賦值了一個(gè)值為0的節(jié)點(diǎn)
輸出結(jié)果如下
0 1 2 3 4 5 6 7 8 9
不忘初心
老王：你不好好種地，你以后長大能干什么
小王：學(xué)算法
老王：學(xué)算法肉盹？昔驱！你數(shù)組、鏈表上忍、棧骤肛、隊(duì)列、堆窍蓝、排序腋颠、查找都整不明白，你學(xué)什么算法
小王：我只學(xué)兩個(gè)有序的鏈表合并
老王：吓笙。淑玫。。
