25. K 个一组翻转链表

零、题目介绍

LeetCode 25题“K个一组翻转链表”是一道关于链表操作的经典难题。题目要求给定一个链表的头节点head和一个正整数k，将链表中的节点每k个一组进行翻转，如果节点总数不是k的整数倍，那么最后剩余的节点保持原有顺序。例如，输入链表[1,2,3,4,5]，k = 2，则输出[2,1,4,3,5]；输入链表[1,2,3,4,5]，k = 3，输出[3,2,1,4,5]。

一、常用解法

迭代法

1. 思路：
   • 首先创建一个哑节点（dummy node），它的 next 指针指向链表头节点 head，用于简化边界处理。
   • 定义一个指针 prevGroupEnd 指向当前已处理完的组的最后一个节点（初始为哑节点），curr 指针指向当前要处理的组的第一个节点。
   • 通过遍历链表，每 k 个节点为一组进行翻转。在每组中，使用类似于单链表反转的方法进行翻转。具体来说，使用三个指针 prev、curr 和 nextNode，prev 初始为 null，curr 为当前组的第一个节点，nextNode 用于暂存 curr 的下一个节点。在循环中，不断将 curr 节点指向前一个节点 prev，同时更新 prev 和 curr，直到处理完一组中的 k 个节点。
   • 处理完一组后，调整指针，将前一组的最后一个节点 prevGroupEnd 的 next 指针指向翻转后的组的头节点（即 prev），并更新 prevGroupEnd 为当前组的最后一个节点（即 curr），继续处理下一组，直到链表结束。
2. 优点：迭代法逻辑较为直观，通过逐步处理每一组节点，易于理解和实现。同时，它可以满足进阶要求，即使用 $O(1)$ 的额外内存空间。

递归法

1. 思路：
   • 递归的基本思想是将问题分解为更小的子问题。对于每 k 个节点一组进行翻转，先处理第一组 k 个节点的翻转，然后递归地处理剩余的链表。
   • 在递归函数中，首先检查链表中剩余的节点数是否大于等于 k。如果是，则找到这 k 个节点中的最后一个节点 endOfGroup，并将这 k 个节点进行翻转。翻转后，第一组的第一个节点变为最后一个节点，原来的最后一个节点变为第一个节点。然后，递归地调用函数处理剩余的链表，并将递归调用返回的头节点连接到当前翻转组的最后一个节点的 next 指针上。
   • 最后返回翻转后的第一组的头节点，即 endOfGroup。
2. 优点：递归法代码相对简洁，能够清晰地表达问题的递归结构，对于理解问题的本质有一定帮助。

二、多语言实现

以下是使用不同语言实现LeetCode 25. K个一组翻转链表的代码，并对算法复杂性、常用解法、关键点和难度、扩展及难度加深题目、应用场合进行分析：

1. Python实现

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    # 创建哑节点，方便处理边界情况
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy

    while True:
        # 检查接下来是否有至少k个节点
        kth_node = group_prev
        for _ in range(k):
            kth_node = kth_node.next
            if not kth_node:
                return dummy.next

        # 记录下一组的起始位置
        group_next = kth_node.next

        # 反转当前组内的节点
        prev, curr = group_prev.next, group_prev.next.next
        for _ in range(k - 1):
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        # 连接反转后的组与之前的节点和之后的节点
        first_node_of_group = group_prev.next  # 原来的第一个节点（现在是最后一个）
        first_node_of_group.next = group_next  # 将该组最后的节点指向下一组的第一个节点
        group_prev.next = kth_node  # 将前一组的最后节点指向前一组反转后的第一个节点

        # 移动到下一组
        group_prev = first_node_of_group

    return dummy.next

2. Java实现

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;

        while (true) {
            int count = 0;
            // 定位当前组的末尾节点
            while (end!= null && count < k) {
                end = end.next;
                count++;
            }
            // 剩余节点不足k个，结束循环
            if (end == null) break;

            // 记录当前组的起始节点和下一组的头节点
            ListNode start = pre.next;
            ListNode nextGroup = end.next;

            // 断开当前组与后续节点的连接
            end.next = null;

            // 翻转当前组
            pre.next = reverse(start);

            // 连接翻转后的尾节点与下一组头节点
            start.next = nextGroup;

            // 更新pre和end到下一组的前驱位置
            pre = start;
            end = pre;
        }

        return dummy.next;
    }

    // 翻转链表的方法
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr!= null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

3. C实现

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 翻转链表的函数
ListNode* reverse(ListNode* head, ListNode* end) {
    ListNode* prev = end;
    ListNode* curr = head;
    ListNode* next;
    while (curr!= end) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// k个一组翻转链表的函数
ListNode* reverseKGroup(ListNode* head, int k) {
    // 创建哑节点
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->val = 0;
    dummy->next = head;
    ListNode* pre = dummy;
    ListNode* end = dummy;

    while (true) {
        int count = 0;
        // 定位当前组的末尾节点
        while (end!= NULL && count < k) {
            end = end->next;
            count++;
        }
        // 剩余节点不足k个，结束循环
        if (end == NULL) break;

        // 记录当前组的起始节点和下一组的头节点
        ListNode* start = pre->next;
        ListNode* nextGroup = end->next;

        // 断开当前组与后续节点的连接
        end->next = NULL;

        // 翻转当前组
        pre->next = reverse(start, end);

        // 连接翻转后的尾节点与下一组头节点
        start->next = nextGroup;

        // 更新pre和end到下一组的前驱位置
        pre = start;
        end = pre;
    }

    return dummy->next;
}

4. C++实现

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* end = dummy;

        while (true) {
            int count = 0;
            // 定位当前组的末尾节点
            while (end!= nullptr && count < k) {
                end = end->next;
                count++;
            }
            // 剩余节点不足k个，结束循环
            if (end == nullptr) break;

            // 记录当前组的起始节点和下一组的头节点
            ListNode* start = pre->next;
            ListNode* nextGroup = end->next;

            // 断开当前组与后续节点的连接
            end->next = nullptr;

            // 翻转当前组
            pre->next = reverse(start);

            // 连接翻转后的尾节点与下一组头节点
            start->next = nextGroup;

            // 更新pre和end到下一组的前驱位置
            pre = start;
            end = pre;
        }

        return dummy->next;
    }

    // 翻转链表的函数
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr!= nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

5. Go实现

package main

import "fmt"

// 定义链表节点结构体
type ListNode struct {
    val  int
    next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    // 创建虚拟头节点
    dummy := &ListNode{0, nil}
    dummy.next = head
    pre := dummy

    for {
        // 检查是否还有至少k个节点
        end := pre
        for i := 0; i < k; i++ {
            end = end.next
            if end == nil {
                return dummy.next
            }
        }

        // 记录当前组的起始节点和下一组的头节点
        start := pre.next
        nextGroup := end.next

        // 断开当前组与后续节点的连接
        end.next = nil

        // 翻转当前组
        pre.next = reverse(start)

        // 连接翻转后的尾节点与下一组头节点
        start.next = nextGroup

        // 更新pre到下一组的前驱位置
        pre = start
    }
}

// 翻转链表的函数
func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr!= nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

算法复杂性分析

• 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 是链表的长度。需要遍历链表中的每个节点一次来进行分组和翻转操作。
• 空间复杂度：给出的代码实现中空间复杂度为 $O(1)$，除了存储链表本身所需的空间外，只使用了常数级别的额外空间来存储指针变量等。

常用解法

• 迭代法：利用指针操作，通过循环找到每 $k$ 个节点的组，然后对每组进行翻转操作，并正确连接前后组。如上述给出的各种语言实现大多采用了这种迭代思路。
• 递归法：可以通过递归的方式来处理每 $k$ 个节点的组。先找到第 $k$ 个节点，然后递归地处理后续的链表，再将当前组翻转并与后续翻转后的链表连接起来。
• 栈法：利用栈的特性，将每 $k$ 个节点依次入栈，然后再出栈，实现节点顺序的反转。这种方法需要额外的空间来存储栈中的节点。

关键点和难度

• 关键点
  • 虚拟头节点的使用：引入虚拟头节点可以简化边界情况的处理，避免单独处理头节点被翻转的特殊情况。
  • 指针的正确操作和保存：需要准确地记录每一组的起始节点、末尾节点、下一组的头节点等，在翻转过程中正确更新指针的指向，以保证链表的连接正确。
  • 分组和判断：要能够正确地将链表按照 $k$ 个节点一组进行划分，并判断剩余节点是否不足 $k$ 个。
• 难度
  • 指针操作的复杂性：在翻转链表和连接节点的过程中，指针的更新和维护容易出错，需要对链表的操作有深入的理解和清晰的逻辑。
  • 边界条件处理：包括虚拟头节点的使用、最后剩余节点不足 $k$ 个的情况等，需要考虑周全，否则容易出现程序错误。

扩展及难度加深题目

• 扩展题目
  • 在链表中存在环的情况下，实现每 $k$ 个节点一组翻转：需要先判断链表是否存在环，然后再考虑在环的情况下如何进行分组翻转。
  • 对链表进行随机分组翻转：不再是固定每 $k$ 个节点一组，而是根据一定的随机规则进行分组，然后翻转每组节点。
• 难度加深题目
  • 每 $k$ 个节点一组翻转，同时对每组内部的节点进行特定排序：例如，每组内部的节点按照节点值的大小进行升序或降序排列后再进行翻转。
  • 在多线程环境下实现每 $k$ 个节点一组翻转：需要考虑线程安全问题，确保在多线程操作链表时不会出现数据竞争等问题。

应用场合

• 数据加密与解密：在某些加密算法中，可能需要对数据进行分组处理和顺序变换，类似于链表节点的分组翻转操作，以增加数据的安全性。
• 图像处理中的像素排序：在图像处理中，对于图像的像素数据可以看作是一个链表结构，通过对像素数据进行分组翻转等操作，可以实现图像的一些特效处理，如图像的旋转、翻转等。
• 数据缓存管理：在内存受限的嵌入式系统或其他系统中，链表常被用于实现数据缓存。通过对缓存中的数据进行分组翻转等操作，可以优化缓存的访问顺序，提高缓存的命中率和数据访问效率。