題目描述

輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。

解法1

可以使用三個輔助指針pHead， last，next
pHead記錄當前節(jié)點，last記錄上一個節(jié)點，next記錄下一個節(jié)點
首先使用next保存當前節(jié)點的下一個節(jié)點，然后將當前節(jié)點的下一個節(jié)點指向last，實現(xiàn)反轉(zhuǎn)
如下圖所示

實現(xiàn)代碼

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是將鏈表按照從頭到尾的順序反轉(zhuǎn)的
可以使用遞歸，通過不斷遞歸深入，實現(xiàn)先從鏈表的尾節(jié)點開始反轉(zhuǎn)
然后通過遞歸的回溯實現(xiàn)按照從尾到頭的順序反轉(zhuǎn)每個節(jié)點
如下圖所示

實現(xiàn)代碼

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