題目描述

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

解法1

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

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

實(shí)現(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