golang合并两个排序的链表

合并两个排序的链表

在golang中，我们经常遇到需要合并两个已排序的链表的场景。本文将介绍如何使用golang来实现这个功能。

问题描述

假设我们有两个已排序的链表，我们需要将它们合并成一个新的已排序的链表。

例如，链表1如下所示：1 -> 3 -> 5 -> 7

链表2如下所示：2 -> 4 -> 6 -> 8

我们希望将这两个链表合并成一个新的链表，结果如下所示：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

解决方案

我们可以使用递归的方式来解决这个问题。首先，我们需要比较两个链表的头节点，将较小的那个节点作为新链表的头节点。然后，我们再递归地调用合并函数，将剩余的节点依次插入到新链表中。

具体的实现如下：

```golang package main import "fmt" type ListNode struct { Val int Next *ListNode } func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 } else { l2.Next = mergeTwoLists(l1, l2.Next) return l2 } } func main() { // 创建两个排序链表 l1 := &ListNode{Val: 1} l1.Next = &ListNode{Val: 3} l1.Next.Next = &ListNode{Val: 5} l1.Next.Next.Next = &ListNode{Val: 7} l2 := &ListNode{Val: 2} l2.Next = &ListNode{Val: 4} l2.Next.Next = &ListNode{Val: 6} l2.Next.Next.Next = &ListNode{Val: 8} // 合并两个链表 mergedList := mergeTwoLists(l1, l2) // 打印结果 for mergedList != nil { fmt.Printf("%d ", mergedList.Val) mergedList = mergedList.Next } } ```

结果

运行以上代码，得到的输出结果即为我们合并后的链表。 综上所述，我们可以通过递归的方式来合并两个排序的链表。