旋转链表(中等难度)

题目概述(简单难度)

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置，k为非负数.

示例 1：

输入：head = [1,2,3,4,5], k = 2

输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4

输出：[2,0,1]

在此附上leetcode链接：

点击此处进入leetcode

思路与代码

思路展现

这道题目我的思路是用快慢指针，思路是这样的：定义两个快慢指针，一个为fast指针，一个为slow指针，fast指针先行走k步，然后slow指针和fast指针同时从当前位置开始向后遍历，当fast指针所指向的节点的next域为null时，此时停止遍历，slow指针所指向的节点即为我们旋转后的链表的尾节点，slow指针所指向的节点的下一个节点即为我们旋转后的链表的头节点.

当然因为这道题目的特殊情况非常多，我也是在不断出错中完善的代码，所以我将代码中的特殊情况待会以代码的形式进行讲解，先来看完整的代码.

代码示例

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
         if(head == null || k < 0){
             return null;
         }
         //特殊情况1:k=0的情况，就是原链表
         if(k==0){
             return head;
         }
         //特殊情况2:链表中只有一个节点的情况，不管k值多少，最后的链表还是其本身，就是原链表
         if(head.next==null){
             return head;
         }
         ListNode slow=head;
         ListNode fast=head;
         //fast指针先走k步
         while(k!=0){
             if(fast.next!=null){
                 fast=fast.next;
                 k--;
              //特殊情况3:当k的值大于链表节点的个数的时候,fast指针每次走到尾节点都需要返回到头节点继续遍历,直到走完k步
             }else{
                 fast=head;
                 k--;
             }
         }
         //fast指针走完k步后，此时slow指针和fast指针开始向后遍历，各走一步
         while(fast.next!=null){
             fast=fast.next;
             slow=slow.next;
         }
          //特殊情况4:假设k值与节点个数相同的情况，此时slow指针与fast指针必相遇,且一定相遇在原链表最后一个节点
         if(slow==fast){
             return head;
         }
         ListNode tmp=slow.next;
         slow.next=null;
         fast.next=head;
         head=tmp;
         return head;
    }
}

特殊情况

特殊情况1

首先当链表为null或者k小于0的时候，直接返回null即可.

特殊情况2

假设链表中此时只有一个节点，说明此时不管k的值为多少，再怎么旋转，都是原链表，所以判断head.next是否为空，如果为空，返回head指针所指向的头节点即可.

特殊情况3

在fast指针先走k步的时候也是存在特殊情况的：

当k的值大于链表长度的时候，此时的fast指针遍历到尾节点时需要重新指回头节点,直到走完k步.

特殊情况4

当fast指针走完k步后，此时slow指针和fast指针同时会从当前位置开始向后遍历.直到fast.next=null的时候停止遍历.

此时会出现一个特殊情况，当k的值与链表的节点个数相同的时候，此时slow指针和fast指针经过遍历后一定会相遇，且一定相遇在原链表的最后一个节点处，同学们下来可以拿链表【1，2】，k=2来做下实验,既然这样，此时返回head指针所指向的头节点即可，因为slow指针指向的节点代表旋转后的链表的尾节点，而这个尾节点正是原链表的尾节点，很显然新的旋转链表的头节点就是原链表的头节点了，并没有发生变化.

核心代码

核心的代码就是以下四句：

         ListNode tmp=slow.next;
         slow.next=null;
         fast.next=head;
         head=tmp;

核心代码的应用场景就是链表中节点的个数，也就是链表长度与k值不相等的情况

当不相等时,此时需要定义一个tmp变量来存储我们slow指针遍历完成后所指向的节点的下一个节点,原因是slow指针所指向的节点作为旋转后的链表的尾节点时,其next域必须置为空，所以此时会失去当前slow指针所指向的节点的下一个节点,而这个节点是要作为新的旋转过后的链表的头节点的，所以需要提前保存这个节点

因为不管fast指针如何遍历，最终fast指针都会指向原链表的尾节点,而我们要做的就是将这个尾节点与原链表的头节点进行相连，这样才能将链表串起来形成旋转过后的链表.

最后将新的链表的头节点也就是tmp赋给我们的头指针head,返回head即可.

总结

1:此算法：

时间复杂度：O(N)

空间复杂度：O(1)

2:此道题目仍然运用了我们的经典思路快慢指针法，他的做法与之前剑指offer中寻找链表倒数第k个节点的做法类似，在此我附上链接，同学们下来可自行复习下寻找链表倒数第k个节点这道题目.