Leetcode 旋转链表

### 解题思路 解决 LeetCode 61 题“旋转链表”的核心思想是找到旋转后的新头节点并重新连接链表。为了高效处理，通常采用以下步骤： - **计算链表长度**：遍历整个链表以确定其长度 `length`。 - **特殊情况判断**：如果 `k == 0` 或者链表为空，则直接返回原头节点。 - **取模运算优化旋转次数**：由于链表旋转 `length` 次后会恢复原状，因此只需要执行 `k % length` 次旋转。 - **快慢指针或前后指针法**：使用双指针方法快速定位新头节点和尾节点。 - **链表拼接**：将链表尾部连接到头部，并在合适的位置断开形成新的链表结构。 --- ### 方法一：快慢指针 + 取模优化 该方法通过快慢指针来寻找新头节点与旧尾部的连接点。 ```java class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || k <= 0) return head; ListNode front = head, behind = head; int len = 0; // 找出链表长度，并调整front指针位置 while (k-- > 0) { front = front.next; len++; if (front == null) { k %= len; front = head; } } // 如果不需要旋转，直接返回原头节点 if (front == head) return head; // 同时移动front和behind，直到front指向最后一个节点 while (front.next != null) { front = front.next; behind = behind.next; } // 调整链表连接关系 ListNode newHead = behind.next; front.next = head; behind.next = null; return newHead; } } ``` --- ### 方法二：整体长度计算 + 切分点查找 此方法首先计算链表总长度，再根据 `k % length` 确定切分点，然后进行节点重连。 ```java class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || k == 0) return head; ListNode node = head; int length = 0; // 计算链表长度 while (node.next != null) { node = node.next; length++; } length++; // 取模优化旋转次数 k = k % length; if (k == 0) return head; // 将链表首尾相连 node.next = head; // 移动指针到断开位置 for (int i = 0; i < length - k; i++) { node = node.next; } // 新头节点为当前节点的下一个节点 ListNode newHead = node.next; node.next = null; return newHead; } } ``` --- ### 方法三：快慢指针 + 明确切分点 该方法明确计算出切分点位置，并通过快慢指针分别定位到关键节点。 ```java class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) return head; int length = 1; ListNode oldTail = head; // 获取链表长度 while (oldTail.next != null) { oldTail = oldTail.next; length++; } // 取模优化 k = k % length; if (k == 0) return head; // 找到新的尾节点 ListNode newTail = head; for (int i = 0; i < length - k - 1; i++) { newTail = newTail.next; } // 新头节点和尾节点的连接 ListNode newHead = newTail.next; newTail.next = null; oldTail.next = head; return newHead; } } ``` --- ### 时间复杂度分析 - **时间复杂度**：`O(n)`，其中 `n` 是链表长度。需要两次遍历链表（一次计算长度，一次调整指针）。 - **空间复杂度**：`O(1)`，仅使用常数级额外空间。 --- ### 总结 以上三种解法均基于快慢指针或前后指针的思想，结合取模操作优化旋转次数，从而避免不必要的重复操作。不同实现方式各有侧重，但核心逻辑相似，适用于不同场景下的链表旋转问题。 ---