Leetcode每日一题 61.旋转链表

¶61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2  
输出：[4,5,1,2,3]  

示例 2：

输入：head = [0,1,2], k = 4  
输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

---

对于这题我们可以直接先将链表连成环，然后断开旋转后的头尾结点就行了。

比如 1->2->3->4->5 我们将 5连上1 ，然后再将3,4断开，这样我们就得到了一个旋转后的链表。

代码如下：

/**
 * 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 == NULL)return NULL;
        int len = 1;
        ListNode * p = head;
        while(p->next!=NULL){
            p = p->next;
            len++;
        }
        
        k=k%len;
        if(k==0)return head;//如果不移动 直接返回表头

        ListNode * q = head;
        for(int i = 0 ; i < len - k - 1 ; i++){
            q = q->next;
        }
        
        p->next = head;
        ListNode * newHead = q->next;
        q->next = NULL;
        return newHead;
    }
};