数据结构
网络
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 次浏览
