0025：K 个一组翻转链表（★★）

Ian

2015-01-25 约 384 字预计阅读 1 分钟次阅读

力扣第 25 题

题目

给你链表的头节点 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

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

分析

0024 升级版

p 一开始指向哑节点
先判断 p 后面是否存在 k 个节点，可以让快指针从 p 开始走 k 步来判断
然后进行反转，可以参考 0092
更新 p 的位置，继续循环直到快指针到空

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dum=p=ListNode(next=head)
        while True:
            fast = p
            for _ in range(k):
                fast = fast.next
                if not fast:
                    return dum.next
            tail = p.next
            for _ in range(k-1):
                head = tail.next
                tail.next = head.next
                head.next = p.next
                p.next = head
            p = tail

50 ms

目录

0025：K 个一组翻转链表（★★）

题目

分析

解答