題目描述

輸入一個鏈表，反轉鏈表後，輸出新鏈表的表頭。

解法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