題目：輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

方法一 遞歸

public class Solution {
    ListNode node = null;
    public ListNode ReverseList(ListNode head) {
        if(head == null ||head.next == null){
            return head;
        }
        node = ReverseList(head.next);
    head.next.next = head;
        head.next = null;
        return node;
    }
}

一般情況下反轉(zhuǎn)的問(wèn)題利用遞歸代碼寫起來(lái)是比較簡(jiǎn)潔的，但是也用調(diào)用棧過(guò)深導(dǎo)致溢出的缺點(diǎn)，并且對(duì)遞歸函數(shù)調(diào)用前后的的代碼塊的特點(diǎn)也有要一定的理解。

• 函數(shù)調(diào)用之后的代碼塊一般都是按照遞歸棧，從棧底向棧頂反向執(zhí)行的。
• 函數(shù)調(diào)用之前的代碼快是從棧頂?shù)綏５讏?zhí)行的。
• 所以判斷遞歸的結(jié)束條件要在遞歸函數(shù)的調(diào)用之前進(jìn)行，
• 而需要進(jìn)行反向的代碼在遞歸函數(shù)調(diào)用之后進(jìn)行。

本題中，最終要返回反轉(zhuǎn)之后的頭結(jié)點(diǎn)，所以

• 可以確定return的值為最后一個(gè)節(jié)點(diǎn)，不斷的向上浮動(dòng)
• 然后就是節(jié)點(diǎn)之間的關(guān)系反轉(zhuǎn)
  開(kāi)始時(shí)第k個(gè)節(jié)點(diǎn)的next指向k+1，要將他反轉(zhuǎn)過(guò)來(lái)變成k+1的next指向k。這個(gè)反轉(zhuǎn)過(guò)程要從后向前進(jìn)行。如果從前向后進(jìn)行，就會(huì)導(dǎo)致1->2, 變成 2->1 和3節(jié)點(diǎn)就斷開(kāi)了。如果是反向的話4->5->6 反轉(zhuǎn)之后是4->5<-6，鏈表仍然是相連接的。

方法二

public class Solution {
    ListNode node;
    public ListNode ReverseList(ListNode head) {
        ListNode first = null;
        ListNode second = null;
        while(head != null){
            first = head.next;
            head.next = second;
            second = head;
            head = first;
        }
        return second;
    }
}

上面使用遞歸的解釋中提到，正向反轉(zhuǎn)的話會(huì)出現(xiàn)鏈表斷裂的情況，找不到下一個(gè)節(jié)點(diǎn)，那么我們可以使用一個(gè)指針一直指向下一個(gè)節(jié)點(diǎn)，然后將這個(gè)指針的next指向上一個(gè)節(jié)點(diǎn)即可。