題目描述
輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭，
解法1
可以使用三個輔助指標pHead， last，next
pHead記錄當前節點，last記錄上一個節點，next記錄下一個節點
首先使用next保存當前節點的下一個節點，然后將當前節點的下一個節點指向last，實作反轉
如下圖所示
實作代碼
public ListNode ReverseList(ListNode pHead)
{
ListNode last = null, next = null;
while(pHead != null){
next = pHead.next;
pHead.next = last;
last = pHead;
pHead = next;
}
return last;
}
解法2
解法1是將鏈表按照從頭到尾的順序反轉的
可以使用遞回，通過不斷遞回深入，實作先從鏈表的尾節點開始反轉
然后通過遞回的回溯實作按照從尾到頭的順序反轉每個節點
如下圖所示
實作代碼
public ListNode ReverseList2(ListNode pHead)
{
if(pHead == null || pHead.next == null) return pHead;
ListNode node = ReverseList2(pHead.next);
pHead.next.next = pHead;
pHead.next = null;
return node;
}
更多演算法題目的完整描述，AC代碼，以及解題思路可以查看GitHub倉庫Algorithm
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/46972.html
標籤：C#