每天一道leetcode61-旋转链表

昨天的题解

题目

每天一道leetcode61. 旋转链表 分类：双指针 中文链接： https://leetcode-cn.com/problems/rotate-list/description/ 英文链接 https://leetcode.com/problems/rotate-list/description/

题目详述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

题目详解

思路

• 首先遍历链表计算链表的长度length,然后用k去对length取余，余数是A，A就是链表需要向右移动的位置，余数是A也就是需要把链表末尾的A个节点移动到链表头部；
• 这里的话需要找到倒数第A个节点，也就是使用双指针，一个fast一个slow，fast先走A步，然后fast与slow一起走，当fast走到链表的末尾（fast.next = null）,那么slow就走到了倒数第(A+1)个节点（这里自己画一个节点链表示意图，比划一下就知道！）
• 然后就是旋转啦~，slow的下一个节点是旋转后的头结点，保存下来以后，注意把slow.next = null(因为slow是旋转后的末尾节点），fast的节点需要进行连接head，因为旋转了，fast.next = head;(这样把前后两部分链表拼接起来~）

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null)
            return head;
        int length = 0;
        ListNode temp = head;
        while(temp != null)
        {
            length++;
            temp = temp.next;
        }
        k = k % length;
        if(k == 0)
            return head;
        ListNode fast = head;
        ListNode slow = head;
        for(int i=0;i<k;i++)
            fast = fast.next;
        while(fast.next != null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode resultHead = slow.next;
        slow.next = null;
        fast.next = head;
        return resultHead;
    }
}

代码讲解

• 11-12 只有头结点或者为空，直接返回
• 14-20行 计算链表长度，然后求余，然后得出来需要旋转多少个节点
• 21-22行 余数为0，直接返回，不需要旋转
• 25-26行 fast先走K步
• 27-31行 slow和fast一起走，直到fast走到最后一个节点，那么slow就走到了倒数第K+1个节点了!
• 32-34行 进行旋转，slow的下一个节点是旋转后的头结点，resultHead保存下来以后，注意把slow.next = null(因为slow是旋转后的末尾节点），fast的节点需要进行连接head，因为旋转了,fast这个节点到了前面了，fast.next = head;(这样把前后两部分链表拼接起来~）