數據結構單鏈表

Question

假設我在一個單鏈表中有一個頭指針H，我該如何在僞代碼中完成這項工作？ 顛倒H指向的單向鏈表中的節點。注意：沒有可以創建的新節點 。

Answer 1

可以通過將問題分解爲第一個節點和其餘節點，倒轉其餘節點，然後將新的最後一個節點指向第一個節點來遞歸求解。遞歸堆棧的每一層的從調用它

reverse(node header){ 

//Return if empty list. 
if (h == null) return 

//Split the problem into first and rest. 
node first = header.start 
node rest = first.next 

//Return if only one node. 
if (rest == null) return 

//reverse the rest of the problem, and then point the end of the rest to the old first. 
header.start = rest 
reverse(header) 
first.next.next = first 

//Set the old first to null, as it is now the last node in the list. 
first.next = null 

//Point the header H to the new first node. 
H.next = rest 

} 

這被簡化爲不使用指針，如果你能在你的僞代碼使用指針水平「休息」節點開始，你可以傳遞一個指針「休息」節點到每個後續的遞歸層。