合并排序列表

本篇文章给大家分享《合并排序列表》，覆盖了Golang的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

今天，我们看另一个链表任务。

创建一个函数来合并 2 个已排序的链表。结果列表应该是使用 2 个列表的节点排序的列表。

为此，我们将使用上一篇文章中的通用链表实现，可以在此处找到

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

逻辑很容易理解。首先，我们设置指向两个列表和结果列表头部的指针。由于我们不知道结果列表的“头”，因此我们创建一个虚拟节点作为占位符（稍后我们将修复该节点）。我们还为结果列表创建一个当前节点 rp。

接下来，我们迭代这 2 个列表。每个列表都有一个当前节点。在每一步中，我们都会查看 2 个当前节点中哪一个具有较小的值，并将该节点放入结果列表中。然后将该列表的当前节点（较小的节点）移动到列表中的下一个节点。我们还需要将结果的当前节点移动到下一个位置。

我们的循环逻辑只是继续执行此操作，直到到达其中一个列表的末尾。此时，我们知道其中一个列表不再有可比较的元素；它们已经在结果列表中。因此，我们可以简单地将另一个列表的剩余节点放在结果的末尾，因为我们知道它们已经排序了。

你会如何做这不同的事情？我们可以优化这个吗？请在评论中告诉我。

谢谢！

这篇文章以及本系列所有文章的代码可以在这里找到

好了，本文到此结束，带大家了解了《合并排序列表》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！