https://leetcode.com/problems/rotate-list/description/
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4 Output:2->0->1->NULLExplanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right:0->1->2->NULLrotate 4 steps to the right:2->0->1->NULL
中文翻譯:
給你一個link list，請你向右選轉k次
然後回傳最後的list head
注意:k可能大於list長度
[Solution]
Find the k-th node from the right(tail) of the list, it is the new head.
Using 2 pointer strategy to increase the performance.
For example:
1->2->3->4->5->NULL, k = 2
The new head is '4', which is the 2-th node from the right of the list.
After you find it, you just need to :
1.connect 5 and 1 (connect old tail to old head)
2.break 3 and 4 (make 3 as new tail, make 4 as new head)
The fast way to find k-th node from right, is using "2 pointers strategy".
First, point p1 and p2 to head node.
Then:
1.p1 move k steps
2.p2 and p1 move forward 1 step at a time, untill p1->next==null.
p1 will be the old tail.
p1 will be the old tail.
p2 will be (k+1)-th from the left(tail), which is the new tail.
p2->next will be k-th from the left, which is the new head.
Since you have the old head & tail, new head & tail, it's easy to build the rotated list.
Since you have the old head & tail, new head & tail, it's easy to build the rotated list.
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
//using "2 pointers strategy" to find the "new head node"
if(!head) return NULL;
ListNode* p1=head;
int len=1;
while(k && p1->next){//1.p1 go k step
k--;
p1=p1->next;
len++;
}
if(k>0){//help to skip redundant iterations
k=(k-1)%len;
p1=head;
while(k && p1->next){
k--;
p1=p1->next;
}
}
ListNode* p2=head;
//2.p2 and p1 go untill p1->next==null
while(p1->next){
p1=p1->next;
p2=p2->next;
}
//3.connect tail & head (p1->next=head)
//3.p2->next is the new head(head = p2->next)
//4.p2 is the new tail(p2->next=null)
p1->next=head;
ListNode* newhead=p2->next;
p2->next=NULL;
return newhead;
}
};
