在 Python 中旋转链表

给定一个单链表的头节点和一个数字 K，开发一个程序，将链表从最后一个节点开始顺时针旋转 K 个位置。

示例

输入-1

输出 1

40 -> 50 -> 10 -> 20 -> 30  

说明

在这种情况下，我们对给定的链表进行了两次旋转。在第一次旋转时，5 是头节点，4 是尾节点，而在第二次旋转链表时，4 是头节点，3 是尾节点。

输入-2

输出 2

30 -> 10 -> 20

说明

这里，我们对链表进行了 4 次旋转。

算法 1 - 通过改变第 k 个节点的 next 指针进行旋转

直观理解

对于这种策略，我们必须保留三个指针：指向 (k + 1)^th 节点、k^th 节点以及 k^th 节点前一个节点的指针。目标是遍历给定的链表直到第 k 个节点，并将 (k + 1)^th 指针处的节点设置为 NULL，然后将链表最后一个节点的 next 指向当前头节点，之后 (k + 1)^th 节点将成为我们链表的新头节点。

算法

1. 检查给定的头节点是否为 null 或 k == 0。如果是，则返回链表。
2. 初始化变量 c 为 1，并初始化另一个变量来存储链表中节点的总数（对于头节点）。
3. 遍历给定的链表直到到达第 k 个节点。
4. 检查当前节点是否为 NULL，或者 k 是否大于或等于链表中节点的总数。在这种情况下，不要更新列表；因此，返回。
5. 现在遍历所有节点直到到达末尾，并将最后一个节点的 next 指向之前的头节点。
6. 最后，将头节点移动到 (k + 1)^th 节点，然后将 (k + 1)^th 节点设置为 None。

代码实现

代码

输出

The original linked list is:
1 4 5 5 7 2 1 5 3 9

The rotated Linked list is:
5 5 7 2 1 5 3 9 1 4

时间复杂度：此方法的时​​间复杂度为 O(n)。这是因为我们遍历了给定的链表一次来旋转链表，其中 n 是链表中的节点数。

空间复杂度：此方法的空间复杂度为 O(1)。它是常数的，因为程序中没有分配额外的空间。

算法 2 - 通过旋转 K 个节点

直观理解

这里的方法与上一个类似。在这种方法中，单链表被转换为类似循环链表，然后从头节点向前移动 k-1 步，但在移动之前，将 (k - 1)^th 节点的 next 设置为 null，并将下一个节点设置为头节点。

算法

1. 确定头节点是否为 null 或 k == 0。如果是，则返回头节点。
2. 将最后一个节点的 next 指向头节点，将单链表转换为循环链表。
3. 遍历此链表到达 (k - 1)^th 个位置，这将是最后一个条目。
4. 遍历循环链表的最后一个节点，并通过将最后一个节点的 next 设置为 None 来中断循环。

代码实现

代码

输出

The original List is:
1 2 3 4 5 6 7 8
The rotated linked list is:
6 7 8 1 2 3 4 5

时间复杂度：此方法的时​​间复杂度为 O(n)。这是因为我们遍历了给定的链表一次来旋转链表，其中 n 是链表中的节点数。

空间复杂度：此方法的空间复杂度为 O(1)。它是常数的，因为程序中没有分配额外的空间。

结论

1. 我们将给定一个单链表的头节点和 K。我们需要开发一个程序，该程序将给定的链表按 K^th 节点顺时针旋转。
2. 例如，如果链表的头节点是 Head: 1 -> 2 -> 3 -> 4 -> 5，整数 K = 3，则结果应为 5 -> 1 -> 2 -> 3 -> 4，表示三次旋转后。
3. 我们学习了两种旋转给定链表的方法：第一种是更改每个 k^th 节点的 next 指针，第二种是旋转 K 个节点。
4. 由于我们只遍历了一次链表，因此两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)。