[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.

這道題是要求將單鏈表循環右移k次，每次移動一個結點。

考慮到k大於或等於鏈表的長度n，所以實際效果等同於循環右移k%n次。

遍歷單鏈表，計算出其長度n，並保存指向最後一個結點的尾指針tail 對k做預處理，k = k % n 順序遍歷單鏈表，定位到第n-k個結點 保存第n-k個結點的後繼結點p，將tail的next置為head,並將原來的Head置為q，同時將第n-k個結點的next置為NULL。

需要注意的空鏈表和n==k的情況。

下面貼上代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getLength(ListNode* head,int& len){
        ListNode* p = head;
        len = 1;
        while (p&&p->next){
            len++;
            p = p->next;
        }
        return p;
    }

    ListNode *rotateRight(ListNode *head, int k) {
        int len;
        if (head){
            ListNode* tail = getLength(head, len);
            k = k%len;
            int count = len - k;
            ListNode* p = head;
            while (p&&count > 1){
                p = p->next;
                count--;
            }
            ListNode* q = p->next;
            p->next = NULL;
            if (q){
                tail->next = head;
                head = q;
            }
        }
        return head;
    }
};