数据结构习题--旋转链表

数据结构习题–旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。注意这里的k可能超过链表的长度
在这里插入图片描述

方法：双指针

分析

旋转K次，我们其实就是相当于找到倒数第K个结点，让其成为头结点，然后让原来链表的伪结点和头相连
当然，注意，这里的k可能大于链表长度，所以我们要让其对链表长度取模

代码

package douobleneedle;public class rotateLinkList {/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}class Solution {public ListNode rotateRight(ListNode head, int k) {// 如果链表为null，或者链表只有一个结点if (head == null || head.next == null){return head;}ListNode fast = head;ListNode slow = head;// 第一次用来记录链表的长度// 第二次，用count来完成寻找倒数第k个结点的前一个结点int count = 0;// 第一次使用count，寻找到链表的长度while (fast != null){fast = fast.next;count++;}// 重新移回fastfast = head;// 通过取模计算最小的旋转次数k = k % count;// 重值countcount = 0;while (fast.next != null){// 寻找倒数第k个结点的前一个结点fast = fast.next;count++;if (count > k){slow = slow.next;}}// 完成重新连接(旋转)fast.next = head;head = slow.next;slow.next = null;return head;}}
}