题目要求
1
2
3
4
5
|
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
|
其实这题的描述有些不妥当，确切的说是将最右侧的节点依次移到最左侧作为头结点，一直移动到右侧第k个节点后结束。
还是以1->2->3->4->5->NULL为例
k=1 结果为：5->1->2->3->4->NULL
k=2 结果为：4->5->1->2->3->NULL
k=3 结果为：3->4->5->1->2->NULL
k=4 结果为：2->3->4->5->1->NULL
k=5 结果为：1->2->3->4->5->NULL
k=6 结果为：5->1->2->3->4->NULL
换句话说 当k的值超过了list的长度len的时候，移动k次等价于移动k%len次
思路一：计算出list长度
即通过一次遍历，找到列表的末节点同时，计算出列表的长度。根据列表的长度，计算k%len，也就是最短等价移动次数。之后利用双指针，保证头指针和尾指针之间的距离始终为k，从而找到右边第k个节点。
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
|
public ListNode (ListNode head, int k) {
if(k==0 || head==null)
return head;
ListNode last = head;
int len = 1;
while(last.next != null){
last = last.next;
len++;
}
k = k%len;
if(k==0)
return head;
ListNode start = new ListNode(0);
start.next = head;
int count = len-k;
while(count > 0){
start = start.next;
大专栏 leetcode61.Rotate List count--;
}
last.next = head;
head = start.next;
start.next = null;
return head;
}
|
思路二：简单优化
其实在某些情况下，k的值并不一定比数组的长度大。这时候还计算数组的长度的话，反而降低了性能。这个时候，可以将遍历的过程和头指针的移动结合起来。如果头指针移动到结尾而k并不是等于0，则可以得知k大于列表长度，同时这个过程还可以得出列表的长度。如果k等于0时，头指针未移动到末尾，则可以继续头指针和尾指针的同时移动，知道头指针到达数组的最后一个元素。
代码如下：
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
|
public ListNode rotateRight(ListNode head, int k) {
if(head == null){
return null;
}
ListNode firstPointer = head;
int length = 0;
while(firstPointer!= null && k > 0){
k--;
firstPointer = firstPointer.next;
length++;
}
if(k == 0){
if(firstPointer == null){
return head;
}
ListNode secondPointer = head;
while(firstPointer != null && firstPointer.next!=null){
secondPointer = secondPointer.next;
firstPointer = firstPointer.next;
}
firstPointer.next = head;
ListNode result = secondPointer.next;
secondPointer.next = null;
return result;
}else{
return rotateRight(head, k%length);
}
}
|