算法_链表_旋转链表

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * 输入：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
 */
public class 旋转链表 {
    /**
     * 方法：链表切割，然后再合并
     */
    public static Node.IntNode rotateRight(Node.IntNode head, int k) {

        //空节点拦截
        if(head==null){
            return null;
        }

        //计算node长度
        int len = 0;
        Node.IntNode tempLen = head;
        while (tempLen != null) {
            len += 1;
            tempLen = tempLen.next;
        }
        //计算拆分链表位置
        int n1Len = len - k % len;

        //第一段链表和第二段链表，最后用于交换位置
        Node.IntNode node1 = new Node.IntNode(-1);
        Node.IntNode node2 = new Node.IntNode(-2);

        //循环进行链表切分
        int pos = 1;
        Node.IntNode tempNode = head;
        while (tempNode != null) {
            int val = tempNode.val;
            if (pos <= n1Len) {
                Node.IntNode newNode = new Node.IntNode(val);
                addNode(node1, newNode);
            } else {
                Node.IntNode newNode2 = new Node.IntNode(val);
                addNode(node2, newNode2);
            }
            pos += 1;
            tempNode = tempNode.next;
        }
        //链表合并
        addNode(node2, node1.next);
        return node2.next;
    }

    static void addNode(Node.IntNode root, Node.IntNode node) {
        Node.IntNode tempRoot = root;
        while (tempRoot.next != null) {
            tempRoot = tempRoot.next;
        }
        tempRoot.next = node;
    }

    /**
     * 方法：循环链表，在从中间切开
     */
    public static Node.IntNode rotateRight2(Node.IntNode head, int k) {
        //排除特殊情况
        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        //计算长度
        int n = 1;
        Node.IntNode ptr = head;
        while (ptr.next != null) {
            ptr = ptr.next;
            ++n;
        }
        //计算切分点
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        ptr.next = head;//连接链表头尾
        while (add-- > 0) {
            ptr = ptr.next;
        }
        Node.IntNode res = ptr.next;
        ptr.next = null;//环形链表切分
        return res;
    }

    public static void main(String[] args) {
        Node.IntNode resNode = rotateRight(null, 10);
        Node.IntNode.printNodes(resNode);
    }
}