SuperMP
V1
2021/04/20阅读:40主题:默认主题
Leetcode刷题 | 第110题:旋转链表
为什么要担心?如果努力了,担心不会让结果变得更好。
61. 旋转链表[1]
题目:给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:输入:head = [1, 2, 3, 4, 5], k = 2,输出:[4, 5, 1, 2, 3]
示例 2:输入:head = [0, 1, 2], k = 4,输出:[2, 0, 1]
提示:链表中节点的数目在范围 [0, 500] 内,-100 <= Node.val <= 100,0 <= k <= 2 * 10^9
分析:设链表的长度为 cnt,实际上,仅需要向右移动 move = k % cnt 次即可。那么,链表将从索引 n - 1 - move 后断开,后半段的最后一个指针将指向前半段的首位置。为了完成上述操作:
-
计算链表的长度 cnt,计算过程中记录最后一个指针的地址 last; -
根据索引 n - 1 - move 定位前半段最后一个位置和后半段的首位置; -
前半段的最后一个位置指向 null; -
后半段的最后一个指针 last 指向前半段的首位置 head; -
后半段的首位置地址,即为旋转链表的头结点。
注意1:当 k = 0, k = cnt 或者 k % cnt == 0 时,旋转链表与原链表相同,无需处理。
注意2:(思路)也可以先将给定的链表连接成环,然后将指定位置断开。
JAVA代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
int cnt = 0, move;
ListNode dummy = head;
ListNode last = null; // 原链表的最后一个位置
while (dummy != null) {
if (dummy.next == null) last = dummy;
dummy = dummy.next;
++cnt;
}
move = k % cnt; // 实际需要移动的次数
if (move == 0) return head;
ListNode early_head = head;
for (int i = 0; i < cnt - move - 1; i++) early_head = early_head.next;
ListNode later_head = early_head.next;
// System.out.println(later_head.val);
early_head.next = null;
last.next = head;
return later_head;
}
}
-
时间复杂度为O(N);空间复杂度为O(1)。

参考资料
旋转链表: https://leetcode-cn.com/problems/rotate-list/
作者介绍
SuperMP
V1