鏈接列表和Sentinal節點

Question

因此，我在作業中被要求合併排序2個不同的排序循環鏈表，而不使用sentinal node allso的列表可以是空的，我的任務是什麼是sentinal node首先是什麼？

Answer 1

一個主要節點是一個不包含真實數據的節點 - 它只是爲了方便實現。

因此，具有4個真實元素的列表可能具有一個或多個額外節點，從而總共創建5個或6個節點。

那些額外的節點可能是佔位符（例如標記您開始合併的位置），指示列表頭部的僞節點或算法設計者可以想到的任何其他節點。

Answer 2

標記節點是您添加到代碼中以避免使用特殊代碼處理簡併的節點。例如，對於合併排序，您可以將一個值爲= INFINITY的節點添加到要合併的兩個列表的末尾，這樣可以確保一旦遇到列表的末尾，就不能超越該列表，因爲值總是大於（或等於）另一個列表中的值。

所以，如果你不使用哨兵，你必須編寫代碼來處理這個。在你的合併例程中，你應該檢查你是否已經達到了目的..