将链表按给定大小分组反转

创建一个函数，该函数可以反转链表中的每 t 个节点（其中 t 是函数的输入）。

示例

算法：reverse(head, t)

• 反转第一个 t 个节点的子列表。在反转时跟踪下一个和前一个节点。让 next 指向下一个节点，prev 指向前一个节点。
• Head -> next = reverse (next, t)（递归地获取列表的其余部分并将两个子列表连接起来）
• 返回 prev（prev 成为新列表的头部）。

下面的插图显示了反转过程的工作原理

给定的技术实现如下

C 语言程序

输出

Given linked list 
11 12 13 14 15 16 17 18 19 
Reversed Linked list 
13 12 11 16 15 14 19 18 17

复杂性分析

• 时间复杂度为 O (n)。

列表只遍历一次，并且包含 'n' 个元素。

• 辅助空间为 O(n/t)。

在递归过程中，将为大小为 n、n/t 或 (n/t)+1 的每个链表进行调用。

这个问题可以用 O(1) 空间复杂度解决。

方法 - 2（空间优化 - 迭代）

此算法需要以下步骤

1. 创建一个复制节点并将其指向输入的头部，例如 duplicate -> next = head。
2. 在 O(N) 时间内确定链表的大小，其中 N 是链表的大小。
3. 对于每个组，初始化三个指针 prior、curr 和 next 来反转 t 个元素。
4. 迭代链表，直到 next!=NULL。
5. curr 指向 previous->next，next 指向 curr 的下一个节点。
6. 然后，使用内部 for 循环，通过以下四个步骤反转特定组
   • curr->next = next->next
   • next->next = prev->next
   • prev->next = next
   • next = curr->next
7. 对于最后一个剩余元素之外的所有组，此 for 循环运行 t-1 次；对于最后一个剩余元素，它运行的次数等于链表长度减一。
8. 为了估计剩余链表的大小，在 for 循环后将计数加 t，cnt -= t。
9. 将 prev 的位置设置为 curr，因此 prev = curr。

上述算法的代码如下。

C 语言程序

C++ 程序

输出

Given linked list 
11 12 13 14 15 16 17 18 19 
Reversed Linked list 
13 12 11 16 15 14 19 18 17

复杂性分析

• 时间复杂度将为 O(N)。

while 循环消耗 O(N/t) 时间，而内部 for 循环消耗 O(t) 时间。

• 辅助空间为 O(1)。

没有使用额外的空间。