题目

解析

首先刚拿到这个题目，并没有非常明确的思路。但是通过观察规律，可以看到，在第一个例子中，其实是将倒数第二个元素开始的一段拼接到了开头。
然后马上试着用这个规律去看看第二个例子，发现虽然K大于链表长度，但是被移动的任然是从倒数第K个开始的。

那么思路一下子就有了：找到倒数第K个元素

找到链表倒数第K个元素

这个各位应该见过很多次了，用快慢指针，快指针先走K步，然后慢指针和快指针同时向前走，当快指针到达链表最后一个元素的时候，慢指针就到了倒数K+1。那么再向前走一步就找到目标元素了。这里为什么不直接找到倒数K呢？因为是为了方便解这道题，后面会说明。

//这里保证K小于链表的长度
public ListNode findK(ListNode head,int k){
	if(head==null)return null;
	ListNode fast = head;
        //快慢指针，找到倒数第K个节点
        //快指针先走K步
        while (k > 0) {
            fast = fast.next;
            k--;
        }
	//慢指针从头部出发
        ListNode slow = head;
        //找到倒数第K个节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
	return slow;
}

旋转链表

通过第二个例子可以看到，K是有可能大于链表的长度，那么我们只需要将链表当成一个循环链表处理一下就可以了。

1. 在循环链表中，让快指针先走K步。
2. 当快指针达到最后一个节点时，慢指针位于倒数K+1个节点
3. 此时慢指针的下一个节点(倒数K)成为旋转结果的头部
4. 将慢指针的next指针指向null
5. 将快指针的next指向原本链表的头部

  ListNode fast = head;
        //快慢指针，找到倒数第K个节点
        //快指针先走K步
        while (k > 0) {
            if (fast.next == null) {
                fast = head;
            } else {
                fast = fast.next;
            }
            k--;
        }
        //如果K为链表长度整数倍，则不用旋转了
        if (fast.equals(head)) {
            return head;
        }
        //慢指针从头部出发
        ListNode slow = head;
        //找到倒数第K+1个节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //从倒数K+1位置截断拼接在头部
        ListNode res = slow.next;
        slow.next = null;
        fast.next = head;
        return res;

因为我们需要将链表截断，并且链表是单向链表，所以是用快慢指针找到的倒数K+1个节点，而不是倒数K个。

仍然有优化空间

这个算法时间复杂度O(N)由K和链表长度的最大值决定。空间复杂度O(1)。
在K非常大的时候，让快指针先走K步是非常耗时的。所以我们可以在这里进行优化，思路就是用一个整数m ,记录快指针走的步数，如果快指针走到了结尾，K任然大于0，则此时m就是链表的长度，可以直接用m对k取余数，快速减小K值，达到快速定位目标位置的目的。
这样优化过后，时间复杂度就是由链表长度决定了，会大大减少平均耗时。