合并排序列表

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

创建一个函数来合并 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 个当前节点中哪一个具有较小的值，并将该节点放入结果列表中。然后将该列表的当前节点（较小的节点）移动到列表中的下一个节点。我们还需要将结果的当前节点移动到下一个位置。

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

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

谢谢！

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

以上是合并排序列表的详细内容。更多信息请关注PHP中文网其他相关文章！