---
id: "20220209"
date: "2022/02/09 10:38:05"
title: "leetcode.Q25.k个一组翻转链表"
tags: ["java", "leetcode", "链表"]
categories:
  - "算法"
  - "leetcode刷题"
---

## 解析思路

leetcode 困难，题目描述[点击这里](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)。

本题属于链表翻转的进阶题，思路如下：

<!-- more -->

1. 添加一个虚拟节点头，方便编码编写
2. 遍历链表，当遍历到k个时，对这k个进行处理，处理过程如下：
   1. 对这k个节点进行翻转
   2. 翻转后处理头尾节点的关系，注意需要记录头节点、头节点之前的一个节点、尾节点和尾节点的下一节点共四个节点，细节看代码
3. 一轮处理完毕后继续遍历，当遍历到k个时继续第2步，直到结束遍历

## 代码

```java
public class Q25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode(), index = head;
        res.next = head;
        int count = 0;
        //left:开始翻转节点的父节点
        //right:结束翻转的节点
        ListNode beforeL = res, l = beforeL.next, r, afterR;
        while (index != null) {
            if (++count == k) {
                //进行翻转
                r = index;
                afterR = index.next;
                reverse(l, count);
                index = l;
                //处理头尾节点关系
                l.next = afterR;
                beforeL.next = r;
                //进行下一轮循环
                beforeL = index;
                l = index.next;
                count = 0;
            }
            index = index.next;
        }
        return res.next;
    }

    /**
     * 翻转start后的n个节点
     *
     * @param start
     * @param n
     */
    private void reverse(ListNode start, int n) {
        //反转节点
        ListNode prev = null;
        for (int i = 0; i < n; i++) {
            ListNode next = start.next;
            start.next = prev;
            prev = start;
            start = next;
        }
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        new Q25().reverseKGroup(node, 3);
    }
}

```