Hard

题目描述

给定一个链表的头节点 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) 额外内存空间的算法吗？

解题思路

解题思路

这道题要求每 k 个节点为一组进行链表翻转，是经典的链表操作题目。

主要思路：

  1. 分组处理：遍历链表，每次取 k 个节点作为一组
  2. 检查长度：确保当前组有足够的 k 个节点，不足则保持原样
  3. 翻转操作：对每组 k 个节点进行翻转
  4. 连接处理：将翻转后的组与前后部分正确连接

具体步骤：

  1. 使用哨兵节点简化边界处理
  2. 用快指针先走 k 步，检查是否有足够节点
  3. 如果节点足够，记录翻转区间的前驱、后继节点
  4. 翻转当前 k 个节点
  5. 重新连接翻转后的链表段
  6. 移动到下一组继续处理

关键点：

  • 翻转过程中要保存好前驱和后继节点的位置
  • 翻转后要正确连接各部分
  • 最后一组不足 k 个节点时保持原序

时间复杂度 O(n)，空间复杂度 O(1)，满足进阶要求。

代码实现

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prevGroup = dummy;
        
        while (true) {
            // 检查剩余节点是否足够k个
            ListNode* kthNode = getKthNode(prevGroup, k);
            if (!kthNode) break;
            
            ListNode* nextGroup = kthNode->next;
            
            // 翻转当前k个节点
            ListNode* prev = nextGroup;
            ListNode* curr = prevGroup->next;
            
            while (curr != nextGroup) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            
            // 连接翻转后的部分
            ListNode* temp = prevGroup->next;
            prevGroup->next = kthNode;
            prevGroup = temp;
        }
        
        return dummy->next;
    }
    
private:
    ListNode* getKthNode(ListNode* start, int k) {
        while (start && k > 0) {
            start = start->next;
            k--;
        }
        return start;
    }
};

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev_group = dummy
        
        while True:
            # 检查剩余节点是否足够k个
            kth_node = self.getKthNode(prev_group, k)
            if not kth_node:
                break
            
            next_group = kth_node.next
            
            # 翻转当前k个节点
            prev = next_group
            curr = prev_group.next
            
            while curr != next_group:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            
            # 连接翻转后的部分
            temp = prev_group.next
            prev_group.next = kth_node
            prev_group = temp
        
        return dummy.next
    
    def getKthNode(self, start: ListNode, k: int) -> Optional[ListNode]:
        while start and k > 0:
            start = start.next
            k -= 1
        return start

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevGroup = dummy;
        
        while (true) {
            // 检查剩余节点是否足够k个
            ListNode kthNode = GetKthNode(prevGroup, k);
            if (kthNode == null) break;
            
            ListNode nextGroup = kthNode.next;
            
            // 翻转当前k个节点
            ListNode prev = nextGroup;
            ListNode curr = prevGroup.next;
            
            while (curr != nextGroup) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            
            // 连接翻转后的部分
            ListNode temp = prevGroup.next;
            prevGroup.next = kthNode;
            prevGroup = temp;
        }
        
        return dummy.next;
    }
    
    private ListNode GetKthNode(ListNode start, int k) {
        while (start != null && k > 0) {
            start = start.next;
            k--;
        }
        return start;
    }
}

var reverseKGroup = function(head, k) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prevGroup = dummy;
    
    while (true) {
        // 检查剩余节点是否足够k个
        let kthNode = getKthNode(prevGroup, k);
        if (!kthNode) break;
        
        let nextGroup = kthNode.next;
        
        // 翻转当前k个节点
        let prev = nextGroup;
        let curr = prevGroup.next;
        
        while (curr !== nextGroup) {
            let next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 连接翻转后的部分
        let temp = prevGroup.next;
        prevGroup.next = kthNode;
        prevGroup = temp;
    }
    
    return dummy.next;
    
    function getKthNode(start, k) {
        while (start && k > 0) {
            start = start.next;
            k--;
        }
        return start;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个节点最多被访问两次（检查和翻转）
空间复杂度O(1) - 只使用常数额外空间，满足进阶要求

相关题目