首页 > 代码库 > [LeetCode] Rotate List 单项链表旋转

[LeetCode] Rotate List 单项链表旋转

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.

 

Hide Tags
 Linked List Two Pointers
 
    这题有点难理解,k 的意思是链表右起第k 个,k 大于链的个数时候,循环读取,所以题目中k =5 的时候直接返回。思路是确定链表断开的地方,有个技巧是一个快指针先遍历k 次,然后快慢指针再一次遍历,如果快指针到尾了,这时候慢指针后于快指针k 次,刚好是右起k 步。
 
 1 #include <iostream> 2 using namespace std; 3  4 /** 5  * Definition for singly-linked list. 6  */ 7 struct ListNode { 8     int val; 9     ListNode *next;10     ListNode(int x) : val(x), next(NULL) {}11 };12 13 class Solution {14 public:15     ListNode *rotateRight(ListNode *head, int k) {16         if(head==NULL||k==0)  return head;17         int cnt =0;18         ListNode * first=head,*slow=head;19         while(cnt<k){20             if(first==NULL) first = head;21             first=first->next;22             cnt++;23         }24         if(first==NULL) return head;25         while(first->next!=NULL){26             first=first->next;27             slow=slow->next;28         }29         first->next=head;30         head = slow->next;31         slow->next = NULL;32         return head;33     }34 };35 36 int main()37 {38 39     return 0;40 }
View Code

 

[LeetCode] Rotate List 单项链表旋转