Go語言程式連線兩個連結串列

在 Go 中，連結串列是一種線性資料結構，包含一個節點，該節點進一步包含兩個欄位，一個是資料，另一個是 next。next 包含後續節點的地址。我們將藉助兩種方法執行此程式。在第一種方法中，連結串列將被用作一系列節點，在第二個示例中，使用不同的變數來執行程式。

方法 1 - 使用連結串列作為一系列節點

此程式將連結串列描述為節點的集合，每個節點都具有一個 Value 和指向列表中下一個節點的指標。joinLists 函式需要兩個連結串列作為引數，並返回一個指向新列表頭的指標，該新列表是透過將第二個列表新增到第一個列表的末尾建立的。為了演示目的，printList 函式用於顯示列表的內容。

演算法

  • 步驟 1 - 建立一個 package main 並宣告程式中的 fmt（格式化包）包，其中 main 生成可執行程式碼，fmt 幫助格式化輸入和輸出。

  • 步驟 2 - 建立一個型別為 node 的結構體，其值為 int 型別，next 指標為 node 型別。

  • 步驟 3 - 在下一步中，建立一個 main 函式，並在該函式中建立兩個要連線的連結串列。

  • 步驟 4 - 從 main 中呼叫 joinLists 函式，並將兩個列表作為輸入。

  • 步驟 5 - 檢視是否有任何一個連結串列為空；如果是，則返回非空連結串列。

  • 步驟 6 - 建立一個指標，初始化為指向第一個連結串列 l1 的頂部。

  • 步驟 7 - 使用當前指標遍歷第一個連結串列，直到到達 current。

  • 步驟 8 - 接下來是 nil，表示列表已結束。接下來是第二個連結串列 l2 的頭部。接下來，返回第一個連結串列的 l1 頭部。

  • 步驟 9 - 然後，可以使用 Next 指標從頭節點到尾節點遍歷連線的連結串列。

  • 步驟 10 - 使用 printList 函式打印合並的連結串列，該語句使用 fmt.Println() 函式執行，其中 ln 表示換行。

示例

在此示例中，我們將使用連結串列作為一系列節點。

package main
import "fmt"
type Node struct {
   Value int
   Next  *Node
}

func main() {
   list1 := &Node{Value: 10, Next: &Node{Value: 20, Next: &Node{Value: 30}}}
   list2 := &Node{Value: 40, Next: &Node{Value: 50, Next: &Node{Value: 60}}}
   joinedList := joinLists(list1, list2)
   fmt.Println("The two lists are merged as follows:")
   printList(joinedList)   //print the merged list
}

func joinLists(li1, li2 *Node) *Node {
   if li1 == nil {
      return li2
   } else if li2 == nil {    //check if the list1 is null return list2 and vice-versa
      return li1
   }

   current := li1
   for current.Next != nil {
      current = current.Next 
   }
   current.Next = li2
   return li1
}

func printList(l *Node) {
   for l != nil {
      fmt.Printf("%d ", l.Value)
      l = l.Next
   }
   fmt.Println()
}

輸出

The two lists are merged as follows:
10 20 30 40 50 60

方法 2：在連結串列中使用不同型別的變數及其型別

此方法採用與上一個示例相同的基本方法，但在變數名稱和型別方面有一些變化。joinLists 函式需要兩個連結串列作為引數，並返回一個指向新列表頭的指標，該新列表是透過將第二個列表新增到第一個列表的末尾建立的。為了演示目的，printList 函式用於顯示列表的內容。

演算法

  • 步驟 1 - 建立一個 package main 並宣告程式中的 fmt（格式化包）包，其中 main 生成可執行程式碼，fmt 幫助格式化輸入和輸出。

  • 步驟 2 - 建立一個型別為 node 的結構體，其值為 int 型別，next 指標為 node 型別。

  • 步驟 3 - 在下一步中，建立一個 main 函式，並在該函式中建立兩個要連線的連結串列。

  • 步驟 4 - 呼叫 joinLists 函式並確定哪個連結串列為空，如果其中任何一個為空，則返回非空連結串列。

  • 步驟 5 - 建立一個指標，其頭部初始化為第一個連結串列 li1。

  • 步驟 6 - 將指標 li1 指向第一個連結串列的頭部。

  • 步驟 7 - 直到 li1，使用 li1 指標遍歷第一個連結串列。

  • 步驟 8 - 接下來是 null，表示列表的末尾已到達。

  • 步驟 9 - 將 li1.next 設定為 li2。

  • 步驟 10 - 然後，返回最頂層的連結串列頭部。

  • 步驟 11 - 然後，透過跟隨 Next 指標，可以從頭節點到尾節點遍歷連線的連結串列。

示例

在此示例中，我們將使用不同的變數和型別來繼續執行。

package main
import "fmt"
type ListNode struct {
   Val  int
   Next *ListNode
}

func main() {
   list1 := &ListNode{Val: 10, Next: &ListNode{Val: 20, Next: &ListNode{Val: 30}}}
   list2 := &ListNode{Val: 40, Next: &ListNode{Val: 50, Next: &ListNode{Val: 60}}}

   joinedList := joinLists(list1, list2)  
   fmt.Println("The two linked lists are joined as follows:")
   printList(joinedList)  //print the lists merged
}

func joinLists(li1, li2 *ListNode) *ListNode {
   if li1 == nil {
      return li2
   } else if li2 == nil { //check if the list1 is null return list2 and vice-verca
      return li1
   }

   head := li1
   for li1.Next != nil {
      li1 = li1.Next
   }
   li1.Next = li2
   return head
}

func printList(l *ListNode) {
   for l != nil {
      fmt.Printf("%d ", l.Val)
      l = l.Next
   }
   fmt.Println()
}

輸出

The two linked lists are joined as follows:
10 20 30 40 50 60

結論

我們使用兩個示例執行了連線兩個連結串列的程式。在第一個示例中，我們將連結串列用作一系列節點，在第二個示例中，我們執行了類似的操作，但使用了不同的變數和型別。

更新於： 2023年2月22日

369 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告