题解 | #链表中的节点每k个一组翻转#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
/*
之前做过一次，强迫症的我想着能不能一次遍历（我这里的代码是两次遍历）就搞定，磕了好久没做出来。这里说下这里的思路吧。
首先要对翻转链表很熟悉，p、q、r三指针翻转链表。而每k个进行翻转，中间的就是一段链表（而不是一个单独的节点），所以应该使用两个指针标定中间一段链表的头和尾（相当于q指针一分为二了）。先创建一个冗余头节点，这样比较好操作。每次就是让pre指针（pre的后继就是subHead)后移，然后让subTail在pre后面后移k次，并检查subTail是不是null。标定subHead、rear(也就是subTail的后继）之后，pre、subHead、subTail、rear四个指针保持不变，然后从subHead顺序遍历并翻转子链表，翻转完了之后更改上述四个指针的指向就可以了。

*/
class ListNode {
    int val;
    ListNode next;
    public ListNode() {
        next = null;
    }
    public ListNode(int v) {
        val = v;
        next = null;
    }
}
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(k == 1) return head;
        ListNode pre = new ListNode();
        pre.next = head;
        ListNode subTail = pre;
        head = pre;
        while(subTail != null) {
            for(int i = 0; i < k; i++) {
                subTail = subTail.next;
                if(subTail == null) break;
            }
            if(subTail != null) {
                ListNode subHead = pre.next, rear = subTail.next;
                ListNode p = subHead, q = subHead.next; //保持四个标定位置的指针不变
                while(q != rear) {
                    ListNode r = q.next;
                    q.next = p;
                    p = q;
                    q = r;
                }
                pre.next = subTail; //更改子链表的头尾节点的连接
                subHead.next = rear;
                pre = subHead;
                subTail = subHead;
            }
        }
        return head.next;
    }
}