061.RotateList.md

61. Rotate List

Question:

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL 

Analysis:

一个指针就够了，原理是先遍历整个链表获得链表长度n，

然后此时把链表头和尾链接起来，在往后走 n - k % n 停下来

此时到达新链表的头结点前一个点，这时断开链表即可

Solution1:

/**
 * 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 (!head) return NULL;
        int n = 1;//计数
        ListNode *cur = head; //创建一个指针 指向head
        while(cur -> next){
            ++n;
            cur = cur -> next;
        }
        //得到了个数n
        cur -> next = head; //尾巴接头部
        int m = n - k % n; //要跑到这里断开列表
        for (int i = 0 ; i < m ; ++i){
            cur = cur -> next;
        }
        ListNode * newhead = cur -> next; //新的头部
        cur -> next = NULL; //这里断开,新的尾部。
        return newhead; //
    }
};

关键部分：

链表的题目，一个指针计数，一个指针连尾部，一个新指针断开。