Leetcode 旋转链表-EW帮帮网

Lee

算法思想和步骤

这道题目要求将链表旋转 k 次，每次将链表的最后一个节点移动到链表的头部。以下是详细的算法思想和步骤：

1. 特殊情况处理

在代码的开头，我们需要处理一些特殊情况：

如果链表为空 (head == null)，直接返回 null。
如果链表只有一个节点 (head.next == null)，无需旋转，直接返回原链表。
如果 k == 0，说明无需旋转，直接返回原链表。

2. 计算链表长度

我们首先需要计算链表的长度 length。这一步通过遍历整个链表完成。

代码：

ListNode current = head;
int length = 1;
while (current.next != null) {
    current = current.next;
    length++;
}

3. 将链表连接成环

通过遍历链表，current 最终指向链表的最后一个节点。此时我们将它的 next 指针指向链表的头部 head，从而将链表变成一个环形链表。

代码：

current.next = head;

4. 计算有效的旋转次数

由于旋转 k 次相当于从链表尾部开始往前移动 k 个节点，而如果 k 比链表长度 length 大，则只需计算 k % length 的结果，因为旋转 length 次会回到原链表。

代码：

k = k % length;
int stepsToNewHead = length - k - 1;

5. 找到新链表的头和尾

新链表的头部是从旧链表的头部往后移动 length - k 步的位置：

我们用一个指针 newTail 从头节点开始，遍历到距离新头部前一个节点的位置（即 length - k - 1）。
新链表的头部 newHead 就是 newTail.next。

代码：

ListNode newTail = head;
for (int i = 0; i < stepsToNewHead; i++) {
    newTail = newTail.next;
}
ListNode newHead = newTail.next;

6. 断开环形链表

找到新头部和新尾部后，我们需要断开环形链表，即将 newTail.next 置为 null。

代码：

newTail.next = null;

7. 返回结果

返回新的头节点 newHead 即可。

算法复杂度分析

时间复杂度：
- 遍历链表一次计算长度：O(n)。
- 第二次遍历找到新头部：O(n)。
- 总时间复杂度为：O(n)。
空间复杂度：
- 使用了常量级别的指针操作，没有额外空间开销，空间复杂度为：O(1)。

代码运行逻辑示例

以示例 1 输入为 head = [1,2,3,4,5], k = 2 为例：

计算链表长度 length = 5。
将链表变成环：1 -> 2 -> 3 -> 4 -> 5 -> 1 (环)。
计算有效旋转次数：k = 2，则 stepsToNewHead = 5 - 2 = 3。
从头节点 1 开始，向后走 3 步，到达节点 3，即 newTail = 3，newHead = 4。
断开环：newTail.next = null。
最终结果链表为 [4,5,1,2,3]。

希望解释清楚了，如有疑问，请随时提出！ 😊

java 实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        //特殊情况处理
        if(head == null || head.next == null || k == 0) return head;

        ListNode current = head;
        int length = 1;
        while(current.next != null) {
            current = current.next;
            length++;
        }
        current.next = head; //形成环
        k = k % length;
        int stepstonewtail = length - k - 1;

        ListNode newtail = head;
        for(int i = 0; i < stepstonewtail; i++) {
            newtail = newtail.next;
        }
        ListNode newHead = newtail.next;
        newtail.next = null; //断环
        return newHead;
    }
}

也就是说，由于环已经形成，所以这部分代码片段中，是通过找tail节点来间接确定newhead节点的，对吗？从head开始确定tail节点需要的移动次数是lengt - k - 1

Leetcode 旋转链表