資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Go語言程式：合併兩個已排序的連結串列
在這篇文章中，我們將編寫Go語言程式來合併兩個已排序的連結串列。連結串列是一組包含資料值和指向列表中下一個節點的next指標的兩個欄位。
連結串列是一種動態資料結構，具有兩個指標head和tail，其中head指向第一個值，tail指向最後一個值。在這裡，我們將使用兩個示例來合併已排序的連結串列。
演示
此演示表示兩個已排序的連結串列“LIST1”和“LIST2”。我們需要將這兩個連結串列合併成一個。
List 1: 1, 2,4 List 2: 1, 3, 4 After merge: 1 1 2 3 4 4
演算法
步驟1 − 建立一個名為ListNode的結構體，它包含兩個欄位：節點的值和指向下一個節點的指標。
步驟2 − 建立一個名為mergeTwoLists的函式，該函式有兩個輸入引數list1和list2，它們是指向ListNode結構體的指標。
步驟3 − 在此步驟中，建立一個虛擬節點，用作新連結串列的頭部，並建立一個尾部節點來遍歷連結串列。
步驟4 − 然後，使用for迴圈檢查兩個列表是否都不為空，如果list1的值小於list2的值，則將tail.next設定為l1，並將l1設定為l1.next。
步驟5 − 如果條件不滿足，則對於list2，將tail.next設定為l2，並將l2設定為l2.next。
步驟6 − 將tail設定為tail.next，如果列表中還有任何剩餘元素，則將下一個tail設定為l1或l2。最後，將合併列表的頭部返回給函式。
步驟7 − 在main函式中，建立兩個具有所需值的列表l1和l2，並將它們作為引數傳遞給函式，合併後的結果將被接收。
步驟8 − 對合並後的列表執行迴圈，並在每次迭代中列印新列表的值。列印語句使用fmt包中的printf函式執行。
示例1
在此示例中，將建立一個虛擬節點指向頭部，並建立一個尾部節點來遍歷列表並使用next指標和值欄位將它們合併。合併後的列表將使用for迴圈列印。
package main
import "fmt"
type ListNode struct {
value int
next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for l1 != nil && l2 != nil {
if l1.value < l2.value {
tail.next = l1
l1 = l1.next
} else {
tail.next = l2
l2 = l2.next
}
tail = tail.next
}
if l1 != nil {
tail.next = l1
} else {
tail.next = l2
}
return dummy.next
}
func main() {
l1 := &ListNode{value: 1}
l1.next = &ListNode{value: 2}
l1.next.next = &ListNode{value: 4}
l2 := &ListNode{value: 1}
l2.next = &ListNode{value: 3}
l2.next.next = &ListNode{value: 4}
merged := mergeTwoLists(l1, l2)
fmt.Println("The merged list l1 and l2 is:")
for merged != nil {
fmt.Printf("%d ", merged.value)
merged = merged.next
}
}
輸出
The merged list l1 and l2 is: 1 1 2 3 4 4
示例2
在此示例中，將使用遞迴方法對第一個和第二個已排序列表進行合併。合併後的列表將使用for迴圈列印。
package main
import "fmt"
type ListNode struct {
value int
next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.value < l2.value {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
func main() {
l1 := &ListNode{value: 1}
l1.next = &ListNode{value: 2}
l1.next.next = &ListNode{value: 4}
l2 := &ListNode{value: 1}
l2.next = &ListNode{value: 3}
l2.next.next = &ListNode{value: 4}
merged := mergeTwoLists(l1, l2)
fmt.Println("The new merged list is:")
for merged != nil {
fmt.Printf("%d ", merged.value)
merged = merged.next
}
}
輸出
The new merged list is: 1 1 2 3 4 4
結論
在這篇文章中，我們研究瞭如何使用兩個示例執行合併兩個已排序連結串列的程式。在第一個示例中，我們使用尾節點遍歷列表併合並節點，而在第二個示例中，我們使用遞迴來合併兩個列表。
646 次瀏覽
