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

非递归方法

使用四个指针标记一条k链，把这条k链断开、翻转、最后再拼接回去

1. 头结点会变，因此使用一个虚拟头结点
2. 使用pre和right两个指针用于找到每个k链的起始位置（的前一个节点）和终止位置
3. 移动right节点到第k个节点处
4. left是pre的后继节点，也是k链的第一个节点；cur是right的后继节点，也就是k链的后继节点
5. 断开k链
6. 翻转链表
7. 翻转后拼接回去就行了，原链表中留了一个pre和一个cur，让pre.next指向翻转后的k链的第一个元素（right）即可，让翻转后的k链的最后一个元素left的next指向原链表中的cur，即可将翻转后的k链拼接回原链表

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if (head == null || head.next == null) return head;
        // 头结点会变，因此使用一个虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // 这两个指针用于找到每个k链的起始位置（的前一个节点）和终止位置
        ListNode pre = dummyHead;
        ListNode right = pre;
        // 移动right节点到第k个节点处
        while (right.next != null){ // 如果right已经是链表的最后一个节点了就不用再找了
            for (int i = 0; i < k && right != null; ++i) {
                right = right.next;
            }
            // 如果最后不足k个节点了就直接返回
            if (right == null) {
                return dummyHead.next;
            }
            // 用于断开k链的两个指针
            ListNode left = pre.next;
            ListNode cur = right.next;
            // 断开k链
            pre.next = null;
            right.next = null;
            // 翻转链表
            reverse(left);
            pre.next = right;
            left.next = cur;
            // 翻转后的链表right为k链第一个节点，left为k链最后一个节点，同时也是下一条k链的前一个节点pre，所以要把pre和right都移动到left的位置，让right在下一个迭代轮次中开始向后移动k位
            pre = left;
            right = pre;
        }
        return dummyHead.next;
    }
    // 翻转链表方法
    private void reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
    }
}