侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【链表, 模拟】K 个一组翻转链表

GabrielxD
2022-04-27 / 0 评论 / 0 点赞 / 38 阅读 / 1,286 字 / 正在检测是否收录...

题目

25. K 个一组翻转链表


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

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

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

示例 1:

image-20220426134946895

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

image-20220426134955967

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:

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

解题

方法一:模拟 迭代 反转链表

思路

对链表以 k 为长度进行分区处理,具体操作:

遍历链表,记录每个区的头节点(partHead),以及头节点的前驱节点(beforePart)用以拼接反转后的区链表(由于整个链表的头节点没有前驱节点,所以新建一个假头(dummy)链接整个链表)。

记录当前遍历的节点的后继节点(oriNext)(如果遍历到的节点是区链表的尾节点,要进行反转区链表,导致破坏其中的指向关系)。

当(curr)遍历到每一个区的尾节点时(i % k == 0):

  • 记录当前区链表的头节点(partHead)用作下一个区链表头节点的前驱节点(partTailAfterReverse)(因为区链表反转后头节点就变成了当前区链表的尾节点,也就是下一个区链表的头节点的前驱节点)
  • 然后把区头节点(partHead)及区长度(k)传入反转方法(reversePart())进行反转,该方法返回反转后区链表的头节点
  • 把反转后的区链表接入原链表
  • 把下一个区链表的头节点(partHead)初始化为原遍历节点的后继节点(oriNext)
  • 把下一个区链表的头节点的前驱节点(beforePart)初始化为当前区链表的尾节点

遍历完成后把长度不够一个区的剩余部分接入原链表即可。
注意返回的是假头的后继节点,因为整个过程中只有假头的指向关系算是没变的。

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // dummy: 假头, beforePart: 区头节点的前驱节点
        ListNode dummy = new ListNode(-1, head), beforePart = dummy;
        // partHead: 区头节点, curr: 当前遍历到的节点, oriNext: 当前遍历到的节点的后继节点
        ListNode partHead = head, curr = head, oriNext;
        // 结束条件: 遍历到链表末端, 增量: curr节点向前推
        for (int i = 1; curr != null; i++, curr = oriNext) {
            // 记录当前遍历的节点的后继节点
            // 因为如果遍历到的节点是区链表的尾节点,要进行反转区链表,导致破坏其中的指向关系
            oriNext = curr.next;
            // 当 curr 遍历到每一个区的尾节点时
            if (i % k == 0) {
                // 记录当前区链表的头节点用作下一个区链表头节点的前驱节点
                // 因为区链表反转后头节点就变成了当前区链表的尾节点 (1)
                // 也就是下一个区链表的头节点的前驱节点
                ListNode partTailAfterReverse = partHead;
                // 把区头节点及区长度传入反转方法进行反转,该方法返回反转后区链表的头节点
                // 并把反转后的区链表接入原链表
                beforePart.next = reversePart(partHead, k);
                // 把下一个区链表的头节点初始化为原遍历节点的后继节点
                partHead = oriNext;
                // 把下一个区链表的头节点的前驱节点初始化为当前区链表的尾节点 原因如上 (1)
                beforePart = partTailAfterReverse;
            }
        }
        // 遍历完成后把长度不够一个区的剩余部分接入原链表
        beforePart.next = partHead;
        // 注意返回的是假头的后继节点,因为整个过程中只有假头的指向关系算是没变的
        return dummy.next;
    }

    public ListNode reversePart(ListNode head, int len) {
        ListNode curr = head, newPrev, newNext = null;
        for (int i = 0; i < len; i++) {
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        return newNext;
    }
}

截断分组结尾反转链表再接回去:

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head);
        ListNode before = dummy, end = dummy;
        while (end != null) {
            for (int i = 0; i < k && end != null; ++i) end = end.next;
            if (end == null) break;
            ListNode begin = before.next;
            ListNode next = end.next;
            end.next = null;
            before.next = reverseList(begin);
            begin.next = next;
            end = before = begin;
        }
        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode curr = head, newNext = null, newPrev;
        while (curr != null) {
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        return newNext;
    }
}
class Solution {
    ListNode* reverseList(ListNode* head) {
        ListNode* curr = head, * newNext = nullptr, * newPrev;
        while (curr) {
            newPrev = curr->next;
            curr->next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        return newNext;
    }

public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* before = dummy, * end = dummy;
        while (end) {
            for (int i = 0; i < k && end; ++i) end = end->next;
            if (!end) break;
            ListNode* begin = before->next;
            ListNode* next = end->next;
            end->next = nullptr;
            before->next = reverseList(begin);
            begin->next = next;
            before = end = begin;
        }
        return dummy->next;
    }
};
0

评论区