# 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