旋转链表

题意

给定一个链表,旋转链表,使得每个节点向右移动 k 个位置,其中 k 是一个非负数

样例

给出链表 1->2->3->4->5->nullk=2

返回 4->5->1->2->3->null

思路

设链表长度为 n,
k = n 时,链表旋转后的结果就是原链表(当 k 为 n 的倍数时,结果也是一样)。

k < n 时,其实旋转链表就是将第 n - k 个元素后的所有元素都放在该链表的头结点之前,并把第 n - k 个元素的下一个节点指向 null 即可。

k > n 时,则说明不止需要旋转一圈,但多旋转一圈其实跟多旋转两圈没什么区别,所以只需要将链表旋转 k % n 个位置即可。

代码实现

1
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
34
35
36
37
38
39
40
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: the List
* @param k: rotate to the right k places
* @return: the list after rotation
*/
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}

//获取链表长度,并得到尾节点的指针。
int len = 1;
ListNode p = head;
while (p.next != null) {
p = p.next;
len++;
}

k = k % len; //去除需要多旋转的圈数
p.next = head; //将链表首尾相连,结成环形。
for (int i = 0; i < len - k; i++) {
p = p.next; //旋转链表
}
head = p.next; //新的链表头
p.next = null; //断开环形链表。
return head;
}
}

原题地址

LintCode:旋转链表