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 * 109

解题思路：这道题还是自己做的，主要是考虑了几点：一个是先计算出链表的长度，因为右移位数k可能很大，我们只需要右移k%(数组长度)即可；另一个是我们数组右移k位，其实相当于第k位变成了链表头，而原先的链表头接到原先的链表尾后面，形成一个新的链表，此时我们返回第k位为链表头的链表即可。

代码 t100 s34 java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null || k==0) return head;
        int len = 1;
        ListNode tail = head;
        while(tail.next!=null){
            tail = tail.next;
            len++;
        }
        tail.next = head;
        k = k % len;
        ListNode cur = head;
        int idx = 1;
        while(idx<len-k){
            cur = cur.next;
            idx++;
        }
        ListNode t = cur.next;
        cur.next = null;
        return t;
    }
}

解题思路：下面这种cpp的方法是7个月前做的，应该还是参考了网上的一些资料，思路都差不多，贴上来一起参考吧。

代码 t45 s50 cpp

/**
 * 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 || !head->next || k==0) return head;
        int len = 1;
        ListNode *t;
        for(t = head;t->next;t=t->next) len++;
        int cut = len - k % len;
        if(cut == len) return head;
        ListNode *dummy = new ListNode(-1), *temp;
        dummy->next = head;
        temp = dummy;
        for(int i = 0; i < cut; i++){
            temp = temp->next;
        }
        ListNode *h = dummy->next;
        dummy->next = temp->next;
        temp->next = nullptr;
        t->next = h;
        return dummy->next;
        
    }
};

参考资料

61. 旋转链表

原文：https://www.cnblogs.com/zhengxch/p/14584907.html