旋转链表

旋转链表

1.想法：

image.png

首先我们可以不每次都找到最后一个元素然后将它作为头结点，即我们得知k后，就可以知道最终的形式
那么我们需要知道以下节点，1.现在的头结点head（已知）2.倒数第k个节点(先去遍历整个链表，然后找到length-k号节点）3.倒数第k个节点的前一个节点（它的未来下一个节点置为null）
例如对于上面的数组我们k=2

image.png

让preKNode.next = null; end.next = head; return LastKNode 这个算法就算完了
后面发现K可能大于length，可以证实，当k==length时就相当于没有反转，那么就可k==0一样

那么就是给k的取模运算

2.代码：

public ListNode rotateRight(ListNode head, int k) {
        if(head == null||head.next == null) return head;
        ListNode newHead = head;
        int length=1;
        while(newHead.next!=null){
            length++;
            newHead = newHead.next;
        }
        k=k%length;
        if(k==0)return head;
        ListNode end = newHead,lastKNode=null,preLastKNode=null;
        newHead = head;
        int count = length-k-1;
        while(count-->0){
            newHead = newHead.next;
        }
        preLastKNode = newHead;
        lastKNode = newHead.next;
        preLastKNode.next=null;
        end.next = head;
        return lastKNode;
    }