今天，我們來看另一個鍊錶任務。
建立一個函數來合併 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中文網其他相關文章！
