【一天一道LeetCode】#61. Rotate List

一天一道LeetCode系列

（一）題目

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.

（二）解題

本題的思路：

1、找到倒數第K個節點

2、将k以後的節點移動到前面來，與頭結點相連。

3、新的頭結點就是倒數第k個節點。

需要注意一下幾種特殊情況：

1、連結清單為空或者連結清單隻有一個節點

2、k的值為0或者k的值大于連結清單的長度

/**
 * 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) {
        if(k==||head == NULL || head->next==NULL) return head;
        ListNode* pkth =  head;//記錄倒數第k個節點
        ListNode* pLast =  head;//記錄最後一個節點
        ListNode* ptemp =NULL;//倒數第K+1個節點
        ListNode* p = head;
        int length = ;
        while(p!=NULL)//求對外連結表的長度
        {
            p=p->next;
            ++length;
        }
        k %=length;//保證k在0~length之間
        if(k==) return head;//k等于0直接傳回head
        while(pLast != NULL && --k) pLast = pLast->next;//找到正數第K個節點
        while(pLast->next !=NULL){//找到倒數第K個節點
            ptemp = pkth;//這裡用到兩個指針，pLast和pkth同時移動，最後pkth就是倒數第K個節點
            pkth = pkth->next;
            pLast = pLast->next;
        }
        ptemp->next = NULL;
        pLast->next = head;//調整連結清單
        return pkth;
    }
};