【LeetCode】链表反转及其衍生问题（3）

（一）基础：链表反转问题

??详见：、206. 反转链表

??（1）三指针。使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。将指针反转后，三个结点依次前移即可。（2）递归方法。同样可以采用递归来实现反转。将头结点之后的链表反转后，再将头结点接到尾部即可。

    //方法一：三指针
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode first=null; 
        ListNode second=head;
        ListNode third=head.next;
        while(third!=null){ 
            second.next=first; //三指针之间的变换
            first=second;
            second=third;
            third=third.next;
        }
        second.next=first;
        return second;
    }

    //方法二：递归
    public ListNode ReverseList(ListNode head) {
         if(head==null||head.next==null)
            return head;
        ListNode temp=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        return temp;   
    }

（二）反转链表II（从m到n）

题目（Medium）：92. 反转链表 II

题目描述：

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

解题思路：

??本题是链表反转的一个延伸，实际上，只要理清楚每一个指针的变化，并不难实现。如下图所示，

??第一步：找到待反转节点的前一个节点。

??第二步：反转m到n这部分。

??第三步：将反转的起点的next指向反转的后面一部分。

??第四步：将第一步找到的节点指向反转以后的头节点。

图片来自：作者：reedfan
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/ji-bai-liao-100de-javayong-hu-by-reedfan-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现：

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null || head.next==null)
            return head;
        ListNode phead=new ListNode(-1); //头结点
        phead.next=head;
        ListNode firstTail=null,cur=phead;
        //走m步，则cur是第m个结点，pre是反转之前最后一个，也就是正常一段的末尾
        for(int i=0;i

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null || head.next==null)
            return head;
        ListNode phead=new ListNode(-1);
        phead.next=head;
        ListNode pre=phead,end=phead;
        while(end.next!=null){
            for(int i=0;i