合併排序列表

今天，我們來看另一個鍊錶任務。

建立一個函數來合併 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中文網其他相關文章！