反转链表是一个很困的题，我前后做了很多次，隔了三个月还是没能完全做出来。我希望今天开始彻底把反转链表搞懂。
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

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;//把当前节点的下一个节点暂存起来
            cur.next = pre;//让当前节点翻转
            pre = cur;//更新前一个节点
            cur = transit;//更新当前节点
        }
    }
}

2 递归法

始终要核心记住递归函数的定义：
输入一个节点head，将以head为起点的链表反转，并返回反转完成后链表的头结点。
输入一个节点head，将以head为起点的链表反转，并返回反转完成后链表的头结点。
输入一个节点head，将以head为起点的链表反转，并返回反转完成后链表的头结点。

class Solution {
    public ListNode reverseList(ListNode head) {
        //始终要核心记住递归函数的定义：
        //输入一个节点head，将以head为起点的链表反转，并返回反转完成后链表的头结点。
        if(head == null || head.next == null) return head;//链表为空或者链表只有一个节点
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last; 
    }
}

3 反转链表的前N个节点

//反转链表的前n个节点
    ListNode pre = null;
    //用于记录前驱节点，当递归到需要反转的最后一个节点时
    //，反转后不应该指向空，所以记录前驱节点
    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 反转部分链表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null) return head;
//相对的，其实如果把left看作第一个节点，就等于反转前n个节点，所以此处使用递归。
        if(left == 1){
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    //反转链表的前n个节点
    ListNode pre = null;
    //用于记录前驱节点，当递归到需要反转的最后一个节点时
    //，反转后不应该指向空，所以记录前驱节点
    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个一组反转链表

/**
 * 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 {
    //首先，整个题的核心思路是，
    //1.先反转以head开头的k个元素；
    //2.将第k+1个元素作为head递归调用reverseKGroup
    //3.将上述两个过程的结果连接起来
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        ListNode a = head;
        ListNode b = head;
        //这个循环作为base case因为不足k个节点的时候，不用翻转，当充足时，把b节点递归到最后。
        for(int i = 0; i < k; i++){
            if(b == null) return head; 
            b = b.next;
        }
        //翻转a到b之间的节点，返回一个新的头结点
        ListNode newNode = reverseK(a, b);
        //递归调用函数，继续翻转，将前面两个结果连接起来
        a.next = reverseKGroup(b, k);
        return newNode;
    }
    //翻转[a,b) 的节点之间的节点，注意左闭右开，采用传统迭代方法
    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;
    }
}