61.旋转链表

下面是题目

下面是题目给出的模板

/**
 * 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) {
        
    }
};

我的思路很简单，就是先计算出要移动几个位置，然后用一个迭代器移动到新的头结点的位置，断开，重连。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //首先还是建立一个dummyNode，因为我不能保证头节点不发生变化
        ListNode *dummy = new ListNode(-1);
        dummy ->next = head;
        ListNode *cur = dummy,*cur2 =dummy;
        int i = 0,j = 0;
        //遍历一边链表，计算出节点数
        while(cur->next)
        {
            i++;
            cur= cur->next;
        }
       //剔除几个特殊情况，当头节点为NULL，直接返回头节点
        //当只有一个节点，或者需要移动的数目是总结点数的倍数的时候,链表不需要发生任何变化
        if(!head) return NULL;
        if(!head->next||k%i==0) return head;
        //然后移动i-(k%i)格。注意，因为k可能是超过i的所以要用 k%i 而不是直接用k
        while( j++ < i-(k%i) )
        {         
            cur2 = cur2->next;
        }
        //现在，cur2移动到了新的尾节点。然后需要做的就是把尾节点cur2断开，并令一个新的头节点
        ListNode *head2 = cur2->next;
        cur2->next = NULL;
        //然后把原来的尾节点与原来的头节点相连接，并返回新的头节点
        cur->next = head;
        return head2;
    }
};