旋转链表

61. 旋转链表 - 力扣（LeetCode）

难度：Medium

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

比如说输入单链表 1 -> 2 -> 3 -> 4 -> 5，k = 2，你的算法需要返回 4 -> 5 -> 1 -> 2 -> 3，即将链表每个节点向右移动 2 个位置。

这个题其实就是将链表的后 k 个节点移动到链表的头部。

把后 k 个节点移动到链表的头部，其实就是让你把链表的前 n - k 个节点和后 k 个节点原地翻转。只需要先将整个链表反转，然后将前 n - k 个节点和后 k 个节点分别反转，就得到了结果。

当然，这个题有一些小细节，比如这个 k 可能大于链表的长度，那么你需要先求出链表的长度 n，然后取模 k = k % n，这样 k 就不会大于链表的长度，且最后得到的结果也是正确的。

反转链表相关代码请去看我之前写的K个一组反转链表。

class Solution {  
    public ListNode rotateRight(ListNode head, int k) {//[1,2] 2  
        if (head == null || k == 0 || head.next == null) {  
            return head;  
        }  
        int length = 0;  
        ListNode cur = head;  
        //计算链表长度  
        while (cur != null) {  
            length++;  
            cur = cur.next;  
        }  
        //处理k  
        if (k > length) {  
            k = k % length;  
            if (k == 0) {  
                return head;  
            }  
        }  
  
        //先反转全部  
        ListNode newHead = reverse(head);  
        ListNode h = newHead;  
        int l = k;  
        while (k > 1) {  
            k--;  
            h = h.next;  
        }  
        //再反转后n-k个  
        h.next = reverse(h.next);  
        //再反转前k个  
        ListNode newHead1 = reverseN(newHead, l);  
        return newHead1;  
    }  
  
    ListNode reverse(ListNode head) {  
        if (head == null || head.next == null) {  
            return head;  
        }  
        ListNode newHead = reverse(head.next);  
        head.next.next = head;  
        head.next = null;  
        return newHead;  
    }  
  
    ListNode after = null;  
  
    ListNode reverseN(ListNode head, int n) {  
        if (n == 1 || head.next == null) {  
            after = head.next;  
            return head;  
        }  
        ListNode newHead = reverseN(head.next, n - 1);  
        head.next.next = head;  
        head.next = after;  
        return newHead;  
    }  
}