算法步骤
旋转链表
- 求链表长度
- 计算实际需要移动的位置k
- 快慢指针法找到倒数第k个节点
- 链表旋转：k节点作为新的链表头，k-1节点作为链表尾，中间部分以循环链表方式连接
复杂度
- 空间复杂度：O(1)
- 时间复杂度：O(n)
代码实现
版本11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34public static ListNode rotateRight(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode tmp = dummy.next;
int n = 0;
//求链表长度
while (tmp != null) {
tmp = tmp.next;
n++;
}
if (n == 0 || k % n == 0) {
return dummy.next;
}
//当成循环链表，n次移动等于没移动，求余后的k为实际需移动的位置数
k = k % n;
//快慢指针求倒数第k个节点
ListNode slow = dummy;
ListNode fast = dummy;
while (k > 0) {
fast = fast.next;
k--;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
//kNode为返回结果的head
ListNode kNode = slow.next;
//原slow节点即为tail
slow.next = null;
//连接原链表的头部
fast.next = head;
return kNode;
}
版本2：快慢指针法，关键是k = k % n1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public static ListNode rotateRight(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy.next;
int n = 1;
//快指针，求链表长度和tail节点
while (fast.next != null) {
fast = fast.next;
n++;
}
//n次移动等于没移动
if (k % n == 0) {
return dummy.next;
}
//当成循环链表，求余后的k为实际需移动的位置数
k = k % n;
ListNode slow = dummy.next;
//求倒数第k个节点
for (int i = 0; i < n - k - 1; i++) {
slow = slow.next;
}
ListNode newHead = slow.next;
slow.next = null;
//连接原链表的头部
fast.next = head;
return newHead;
}