Golang 合并两个已排序链表

在本文中，我们将编写Go语言程序来合并两个已排序的链表。链表是一组具有值（即数据）和指向列表中下一个节点的下一个指针的两个字段。

链表是一种动态数据结构，具有两个指针head和tail，其中head指向第一个值，tail指向最后一个值。在这里，我们将使用两个示例来合并已排序的链表。

演示

这个演示代表了两个已排序的链表“LIST1”和“LIST2”。我们需要将这两个链表合并为一个。

List 1: 1, 2,4
List 2: 1, 3, 4
After merge: 1 1 2 3 4 4

步骤

第一步 - 创建一个ListNode结构体，其中包含两个字段值，即节点的值和指向下个节点的指针
第二步 - 创建一个名为mergeTwoLists的函数，它有两个输入参数，list1和list2，这两个参数指向ListNode结构体
第三步 - 在这一步中，创建一个虚拟节点作为新列表的头部，以及一个尾部节点用于遍历列表
第四步 - 然后，使用一个for循环来检查两个列表是否都不为空，然后检查列表一的值是否小于列表二的值，如果是，则设置tail.next为l1，并将l1设置为l1.next
第五步 - 如果条件不满足，那么对于列表二，将tail.next设置为l2，并将l2设置为l2.next
第六步 - 将tail设置为tail.next，并且如果列表中还剩余元素，则将下一个tail设置为l1或l2。最后，将合并后的列表头部返回给函数
第七步 - 在主函数中，创建两个具有所需值的列表l1和l2，并将它们作为参数传递给函数，合并后的列表将作为输出接收
第八步 - 在merged上运行一个循环，并在每次迭代中打印新列表的值。使用fmt包中的printf语句执行打印操作。

示例1

在这个示例中，将创建一个虚拟节点指向头部，创建一个尾部来遍历列表并使用next指针和value字段将它们合并。使用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
   }
}