【题目】
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
示例1.png
输入： head = [1,2,3,4,5], k = 2
输出： [4,5,1,2,3]
示例 2：
示例2.png
输入： head = [0,1,2], k = 4
输出： [2,0,1]
提示：
- 链表中节点的数目在范围
[0, 500]内 - -100 <= Node.val <= 100
- 0 <= k <= 2 *
【题目解析】
解题方法
-
计算链表长度：遍历链表，计算出链表的总长度
n。 - 连接链表尾部与头部：将链表的尾部与头部连接成环。
-
找到新的头节点和尾节点：计算新的头节点应该在的位置，它应该是从原链表头部向后移动
n - k % n个位置（k % n是为了处理k大于链表长度的情况）。同时，新的尾节点就是新头节点的前一个节点。 - 断开环：在新的尾节点处断开环，确定新的链表头和尾。
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next or k == 0:
return head
# 计算链表长度并形成环
length = 1
current = head
while current.next:
current = current.next
length += 1
current.next = head
# 找到新的头节点和尾节点
steps_to_new_head = length - k % length
new_tail = head
for _ in range(steps_to_new_head - 1):
new_tail = new_tail.next
new_head = new_tail.next
# 断开环
new_tail.next = None
return new_head
执行效率
image.png
【总结】
适用问题类型
- 链表的旋转和重新定位问题。
- 当需要在链表中进行环形操作时，如循环移动、寻找特定位置节点等。
解决算法：链表环形化处理法
- 核心思想：先将链表连接成环，根据旋转次数找到新的头尾节点，最后断开环形链表形成新的线性链表。
算法特点
- 直观易懂：通过将链表首尾相连形成环，直接模拟旋转的过程，使得问题变得直观易理解。
- 高效：只需遍历链表两次，第一次计算链表长度并形成环，第二次找到并断开新的头尾节点。
- 空间节约：不需要额外的存储空间，只通过几个指针变量即可完成所有操作。
时间复杂度与空间复杂度
-
时间复杂度：
O(n)，其中n是链表的节点数量。算法中主要的时间开销在于遍历链表计算长度及找到新的头尾节点上。 -
空间复杂度：
O(1)，算法的空间消耗仅有几个用于指针移动的变量，与链表长度无关。
实践意义
这种方法为链表操作提供了一种高效且直观的解决策略，特别是在面对链表旋转、分割、重组等问题时，能够灵活且高效地进行处理。通过环形链表的概念，我们可以更深入地理解链表的性质和操作技巧，对于提升链表操作的熟练度和解决实际问题具有重要意义。此外，这种方法的思想也可以应用于其他需要环形处理的数据结构问题中，展现了算法设计中的创新性和实用性。
