連結清單04--合并兩個排序的連結清單-jz16
- 題目概述
- 解析&參考答案
- 注意事項
- 說明
題目概述
-
算法說明
輸入兩個單調遞增的連結清單,輸出兩個連結清單合成後的連結清單,當然我們需要合成後的連結清單滿足單調不減規則。
-
測試用例
輸入:
{1,3,5},{2,4,6}
輸出:
{1,2,3,4,5,6}
解析&參考答案
-
解析
方法1:使用遞歸方法,每次擷取一個head,head.Next 為下一個遞歸的傳回。
- 參考答案
vim jz16.go
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func CreateList(array []int) *ListNode {
if len(array) == 0 {
return nil
}
head := &ListNode{array[0], nil}
p := head
for i, val := range array {
if i == 0 {
} else {
item := &ListNode{val, nil}
p.Next = item
p = p.Next
}
}
return head
}
func PrintList(head *ListNode) {
if head == nil {
fmt.Print("nil")
} else {
p := head
for p != nil {
if p.Next != nil {
fmt.Printf("%d->", p.Val)
} else {
fmt.Printf("%d\n", p.Val)
}
p = p.Next
}
}
}
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
if pHead1 == nil {
return pHead2
}
if pHead2 == nil {
return pHead1
}
var head *ListNode = nil
if pHead1.Val <= pHead2.Val {
head = pHead1
head.Next = Merge(pHead1.Next, pHead2)
} else {
head = pHead2
head.Next = Merge(pHead2.Next, pHead1)
}
return head
}
func main() {
array1 := []int{1, 3, 5}
array2 := []int{2, 4, 6}
head1 := CreateList(array1)
head2 := CreateList(array2)
head3 := Merge(head1, head2)
PrintList(head1)
PrintList(head2)
PrintList(head3)
}
注意事項
- to add
說明
- 目前使用 go1.15.8
-
參考 牛客網--劍指offer
标題中jzn(n為具體數字)代表牛客網劍指offer系列第n号題目,例如 jz01 代表牛客網劍指offer中01号題目。
注意!!!
- 筆者最近在學習 golang,是以趁機通過資料結構和算法來進一步熟悉下go語言
- 目前算法主要來源于劍指 offer,後續會進一步補充 LeetCode 上重要算法,以及一些經典算法
- 此處答案僅為參考,不一定是最優解,歡迎感興趣的讀者在評論區提供更優解