题目主要信息

给定链表的头节点，旋转链表，将链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。

即，例如链表 ： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3

方法一：直接求解

具体方法

按照下面的步骤处理即可

• 1、求出链表的长度
• 2、将链表闭合
• 3、求出旋转后的链表的首节点
• 4、断链操作

代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateLinkedList (ListNode head, int k) {
        // write code here
        if(head == null)
            return null;
        int len = 1;
        // 求出链表长度
        ListNode temp = head;
        while(temp.next !=null)
        {
            len++;
            temp = temp.next;
        }
        //旋转后链表的首节点
        int p = len -  k % len;
        temp.next = head;
        //找到首节点
        while(p>0){
            temp = temp.next;
            p--;
        }
        //断链
        ListNode res = temp.next;
        temp.next = null;
        return res;
        
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历一次链表

• 空间复杂度：$O(1)O(1)$，我们只需要常数的空间存储若干变量。

方法二：双指针

具体方法

因为k有可能大于链表长度，所以首先获取一下链表长度len。如果k % len == 0，等于不用旋转，直接返回头结点。否则：

• 快指针先走k步，然后慢指针和快指针一起走。
• 快指针走到链表尾部时，慢指针刚好走到旋转链表的尾部。把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一节点的联系。
• 返回结束时慢指针指向节点的下一节点。

代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateLinkedList (ListNode head, int k) {
        //特殊情况直接返回
        if(head == null || k == 0){
            return head;
        }
        ListNode temp = head;
        ListNode fast = head;
        ListNode slow = head;
        int len = 0;
        //求链表长度
        while(head != null){
            head = head.next;
            len++;
        }
        if(k % len == 0){
            return temp;
        }
        //快指针先走k步
        while((k % len) > 0){
            k--;
            fast = fast.next;
        }
        //两个一起走
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode result = slow.next;
        slow.next = null;
        fast.next = temp;
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历一次链表

• 空间复杂度：$O(1)O(1)$，我们只需要常数的空间存储若干变量。