个人技术分享

题目描述：

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

输入：

head = [1,2,3,4,5], k = 2

输出：

[4,5,1,2,3]

代码描述：

/**
 * 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) {
            // 链表长度为1或者0，移动数为0的情况
            return head;
        }
        
        int length = 0;// k大于链表长度时，length为链表长度，判断是否进行递归调用
        ListNode low = head;// 指向移动之后的链表的尾结点
        ListNode high = head;// 指向移动之前的链表的尾结点
        // 确定high的第一次指向
        for (int i = 0; i < k; i++) {
            high = high.next;
            length++;
            if (high == null) {// 如果移动数 > 链表长度，则递归调用一次
                return rotateRight(head, k % length);// 对k取模
            }
        }
        
        while (high.next != null) {// 两个指针之间要保持相对位置
            low = low.next;// 指向距离尾部结点的前（链表长度-k）个单位的结点
            high = high.next;// 指向当前链表尾部
        }
        
        high.next = head;// 初始尾结点指向初始头结点，形成循环链表
        head = low.next;// 头指针指向移动之后的头结点，也就是循环链表的尾结点的下一个结点
        low.next = null;// 将移动之后的链表的尾结点指向null，即断开链表
        return head;
    }
}