每天一道leetcode61-旋转链表
- 2019 年 10 月 4 日
- 筆記
昨天的题解
题目
每天一道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;(这样把前后两部分链表拼接起来~）
