当前位置：首页 > article >正文

LeetCode25:K个一组翻转链表

article 2024/11/5 2:12:07

原题地址：. - 力扣（LeetCode）

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

实现思路

定义节点：使用ListNode类表示链表节点。

设置虚拟头节点：使用一个虚拟头节点（hair）来处理链表的头部，使得处理操作更加简洁。

遍历链表：使用一个指针head从链表头部开始遍历，找到每一组k个节点：

通过一个循环检查剩余的节点是否至少有k个。
如果不足k个，返回结果（即未变更的链表部分）。

反转k个节点：使用myReverse方法反转找到的k个节点：

该方法接收头节点和尾节点，并逐步将节点的指向反转，最终返回新的头和尾。

重新链接链表：将反转后的子链表连接回原链表：

更新pre.next指向反转后的头节点。
更新反转后的尾节点指向接下来的节点。

更新指针：继续循环，更新pre和head以处理下一个k个节点。

源码实现

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 创建一个虚拟头节点，简化边界处理
        ListNode hair = new ListNode(0);
        hair.next = head; // 虚拟节点指向原链表的头
        ListNode pre = hair; // 用于连接反转后的链表

        // 遍历链表
        while (head != null) {
            ListNode tail = pre; // 每次从pre开始

            // 检查剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next; // 移动tail指针
                if (tail == null) {
                    return hair.next; // 如果不足k个，直接返回
                }
            }

            ListNode nex = tail.next; // 记录下一部分的起始节点
            // 反转k个节点
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0]; // 新的头节点
            tail = reverse[1]; // 新的尾节点

            // 将反转后的子链表接回原链表
            pre.next = head; // pre指向新的头节点
            tail.next = nex; // 新尾节点指向下一部分的起始节点
            pre = tail; // 更新pre
            head = tail.next; // 更新head指向下一组
        }

        return hair.next; // 返回新链表的头
    }

    // 反转链表的方法，返回新的头和尾
    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next; // prev指向tail的下一个
        ListNode p = head; // p用于遍历反转

        // 逐步反转节点
        while (prev != tail) {
            ListNode nex = p.next; // 记录下一个节点
            p.next = prev; // 反转当前节点
            prev = p; // prev移动到当前节点
            p = nex; // p移动到下一个节点
        }

        return new ListNode[]{tail, head}; // 返回新的尾和头
    }
}