# 61 - Rotate List
解法一 -
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
// Rule out corner cases
if(head == nullptr or head->next == nullptr) {
return head;
}
// Calculate the length of list
int n = 1;
ListNode* ptr = head;
while(ptr->next != nullptr) {
ptr = ptr->next;
++n;
}
k = k % n;
if(k == 0) {
return head;
}
// Start changing the pointers
ListNode* dummyHead = new ListNode(-1);
dummyHead->next = head;
ListNode* newTail = dummyHead;
ListNode* newHead = head;
ListNode* oldTail = ptr;
// Move to the newHead
for(int i = 0; i < n-k; ++i) {
newHead = newHead->next;
newTail = newTail->next;
}
dummyHead->next = newHead;
oldTail->next = head;
newTail->next = nullptr;
return dummyHead->next;
}
};
Last updated