C++程序按块旋转链表

题目描述

给定一个链表，每k个节点一组进行翻转，返回翻转后的链表。

k是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么将最后剩余的节点保持原样。

例子：

给定这个链表：1->2->3->4->5

当k=2时，应当返回: 2->1->4->3->5

当k=3时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。

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

解题思路

首先，我们需要区分出哪些节点需要进行旋转，哪些节点是不需要进行旋转的。以k=3为例，我们可以将链表看做这样的：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> …

我们将这些节点按组分配，每组包含k=3个节点，分配之后的结果如下：

[1 -> 2 -> 3] [4 -> 5 -> 6] [7 -> 8 -> 9] …

我们可以看到，每个组的第一个节点就是该组需要进行旋转的节点。

接下来，我们从头到尾遍历每个组的第一个节点，并进行旋转。我们以[1 -> 2 -> 3]组为例，旋转前的链表为：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> …

旋转后的链表应为：

3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> …

为了完成这个旋转操作，我们需要将每个节点的next指向其前一个节点。

最后，我们将旋转后的每个组连接起来即可得到最终的结果。下面是完整的C++代码：

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* new_head = new ListNode(0);  // 创建一个新的头节点，方便链表操作
    new_head->next = head;

    ListNode* pre = new_head;
    ListNode* end = new_head;

    while (end->next != NULL) {
        for (int i = 0; i < k && end != NULL; i++) end = end->next;  // 找到每个组的末尾节点，注意负数节点需要单独处理
        if (end == NULL) break;

        ListNode* start = pre->next;
        ListNode* next = end->next;

        end->next = NULL;  // 断开链表，方便操作

        pre->next = reverseList(start);  // 翻转当前组内的链表

        start->next = next;  // 恢复链表连接

        pre = start;  // 更新pre、end节点
        end = start;
    }

    return new_head->next;
}

ListNode* reverseList(ListNode* head) {  // 翻转链表
    if (head == NULL || head->next == NULL) return head;

    ListNode* new_head = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return new_head;
}

注释中已经解释了每个操作的含义，这里不再重复。

这个算法的时间复杂度为O(n)，其中n为链表的长度。空间复杂度为O(1)，符合题目要求。