[数据结构与算法]链表中每k个节点一组反转算法

地址：

https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=188&&tqId=38557&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

代码：

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head==null||head.next==null||k==1){
            return head;
        }
        int t = k-1;
        ListNode p2 = head;// p2不断往下走，一直走到k
        ListNode p1 = head;
        ListNode p0 = null;
        while(p2!=null){
            if(t!=0){
                p2 = p2.next;// 指针就不指向head了
                t--;
            }
            if(t==0&&p2!=null){
                reverse(p1,p2);
                if (p0 == null) {
                    head = p2;
                } else {
                    p0.next = p2;
                }
                p0 = p1;// p0指向上一次的尾部************
                p1 = p1.next;
                p2 = p1;
                t=k-1;
            }
        }
        return head;
    }
    public void reverse(ListNode head, ListNode tail) {
        // 翻转头和尾的这部分链表，头无所谓，尾部是要和所在链表的下一个节点相连的
        // 维护一个指针，不断的指向头部p
        // 维护一个指针，指向要拿出来的节点p2
        // 维护一个指针，指向迭代的头部p1,这个头部是要变成尾部
        ListNode p1=head,p2=head.next,p=head,last = tail.next;
        while(p2!=null&&p2!=last){
            p1.next = p2.next; // p1不变，取出p2
            p2.next = p; // p2放在头部
            p = p2; // p保持在头部
            p2 = p1.next;// p2前进
        }
    }
}