力扣反转链表系列【25. K 个一组翻转链表】——由易到难，一次刷通！！！

力扣《反转链表》系列文章目录

刷题次序，由易到难，一次刷通！！！

题目	题解
206. 反转链表	反转链表的全部 题解1
92. 反转链表 II	反转链表的指定段 题解2
24. 两两交换链表中的节点	两个一组反转链表 题解3
25. K 个一组翻转链表	K 个一组反转链表

一、题目

二、解题思路

原链表 k 个 k 个节点一组进行翻转，若是待翻转节点个数小于 k 个则不需要进行翻转。因此，首先需要对原链表进行节点个数的统计。与92. 反转链表 II 类似，依次进行 k 个连续节点的翻转。

三、代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计链表节点总个数
        ListNode cur = head;
        int cnt = 0;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        ListNode dummy = new ListNode(0, head);// 创建 dummy node 简化边界条件的处理
        ListNode p0 = dummy;// 上一个节点
        ListNode pre = null;
        cur = head;
        while (cnt >= k) {// 若未反转的节点个数小于 k 则不需要反转
            // k 个节点为一组进行反转
            for(int i = 0; i < k; i++) {
                ListNode nxt = cur.next;// 保存未反转的下一节点
                cur.next = pre;// 反转
                pre = cur;// 更新
                cur = nxt;// 更新
            }
            // 正确连接回原链表
            ListNode tmp = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = tmp;

            // 未反转节点个数减少 k 个
            cnt -= k;
        }
        return dummy.next;
    }
}

原文地址：https://blog.csdn.net/J_pluto/article/details/142439432

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！