反轉(zhuǎn)鏈表是一個(gè)很困的題坪哄，我前后做了很多次，隔了三個(gè)月還是沒能完全做出來势篡。我希望今天開始徹底把反轉(zhuǎn)鏈表搞懂翩肌。
題目：給你單鏈表的頭節(jié)點(diǎn) head ，請你反轉(zhuǎn)鏈表禁悠，并返回反轉(zhuǎn)后的鏈表念祭。

image.png

image.png

image.png

image.png

1 雙指針法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode transit = cur.next;//把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)暫存起來
            cur.next = pre;//讓當(dāng)前節(jié)點(diǎn)翻轉(zhuǎn)
            pre = cur;//更新前一個(gè)節(jié)點(diǎn)
            cur = transit;//更新當(dāng)前節(jié)點(diǎn)
        }
    }
}

2 遞歸法

始終要核心記住遞歸函數(shù)的定義：
輸入一個(gè)節(jié)點(diǎn)head绷蹲，將以head為起點(diǎn)的鏈表反轉(zhuǎn)棒卷，并返回反轉(zhuǎn)完成后鏈表的頭結(jié)點(diǎn)顾孽。
輸入一個(gè)節(jié)點(diǎn)head祝钢，將以head為起點(diǎn)的鏈表反轉(zhuǎn)比规，并返回反轉(zhuǎn)完成后鏈表的頭結(jié)點(diǎn)。
輸入一個(gè)節(jié)點(diǎn)head拦英，將以head為起點(diǎn)的鏈表反轉(zhuǎn)蜒什，并返回反轉(zhuǎn)完成后鏈表的頭結(jié)點(diǎn)。

class Solution {
    public ListNode reverseList(ListNode head) {
        //始終要核心記住遞歸函數(shù)的定義：
        //輸入一個(gè)節(jié)點(diǎn)head疤估，將以head為起點(diǎn)的鏈表反轉(zhuǎn)灾常，并返回反轉(zhuǎn)完成后鏈表的頭結(jié)點(diǎn)。
        if(head == null || head.next == null) return head;//鏈表為空或者鏈表只有一個(gè)節(jié)點(diǎn)
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last; 
    }
}

3 反轉(zhuǎn)鏈表的前N個(gè)節(jié)點(diǎn)

//反轉(zhuǎn)鏈表的前n個(gè)節(jié)點(diǎn)
    ListNode pre = null;
    //用于記錄前驅(qū)節(jié)點(diǎn)铃拇，當(dāng)遞歸到需要反轉(zhuǎn)的最后一個(gè)節(jié)點(diǎn)時(shí)
    //钞瀑，反轉(zhuǎn)后不應(yīng)該指向空，所以記錄前驅(qū)節(jié)點(diǎn)
    public ListNode reverseN(ListNode head, int n){
        if(n == 1){
            pre = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = pre;
        return last;
    }

4 反轉(zhuǎn)部分鏈表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null) return head;
//相對的慷荔，其實(shí)如果把left看作第一個(gè)節(jié)點(diǎn)雕什，就等于反轉(zhuǎn)前n個(gè)節(jié)點(diǎn)，所以此處使用遞歸显晶。
        if(left == 1){
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    //反轉(zhuǎn)鏈表的前n個(gè)節(jié)點(diǎn)
    ListNode pre = null;
    //用于記錄前驅(qū)節(jié)點(diǎn)贷岸，當(dāng)遞歸到需要反轉(zhuǎn)的最后一個(gè)節(jié)點(diǎn)時(shí)
    //，反轉(zhuǎn)后不應(yīng)該指向空磷雇，所以記錄前驅(qū)節(jié)點(diǎn)
    public ListNode reverseN(ListNode head, int n){
        if(n == 1){
            pre = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = pre;
        return last;
    }
}

5 K個(gè)一組反轉(zhuǎn)鏈表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //首先偿警，整個(gè)題的核心思路是，
    //1.先反轉(zhuǎn)以head開頭的k個(gè)元素唯笙；
    //2.將第k+1個(gè)元素作為head遞歸調(diào)用reverseKGroup
    //3.將上述兩個(gè)過程的結(jié)果連接起來
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        ListNode a = head;
        ListNode b = head;
        //這個(gè)循環(huán)作為base case因?yàn)椴蛔鉱個(gè)節(jié)點(diǎn)的時(shí)候螟蒸，不用翻轉(zhuǎn)，當(dāng)充足時(shí)崩掘，把b節(jié)點(diǎn)遞歸到最后尿庐。
        for(int i = 0; i < k; i++){
            if(b == null) return head; 
            b = b.next;
        }
        //翻轉(zhuǎn)a到b之間的節(jié)點(diǎn)，返回一個(gè)新的頭結(jié)點(diǎn)
        ListNode newNode = reverseK(a, b);
        //遞歸調(diào)用函數(shù)呢堰，繼續(xù)翻轉(zhuǎn)抄瑟，將前面兩個(gè)結(jié)果連接起來
        a.next = reverseKGroup(b, k);
        return newNode;
    }
    //翻轉(zhuǎn)[a,b) 的節(jié)點(diǎn)之間的節(jié)點(diǎn)，注意左閉右開枉疼，采用傳統(tǒng)迭代方法
    public ListNode reverseK(ListNode a, ListNode b){
        ListNode pre = null;
        ListNode cur = a;
        while(cur != b){
            ListNode mid = cur.next;
            cur.next = pre;
            pre = cur;
            cur = mid;
        }
        return pre;
    }
}