题目描述

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置

示例

image-20211017090756152

题解

  1. 计算出链表长度
  2. 新链表头节点位置就是k = k mod len
  3. 维护快慢指针,快指针先走k步,随后快慢指针共同向前走,直到到达链表末尾
  4. 让快指针指向链表head节点,使其成环
  5. 从慢节点位置处断开即可称为旋转后的链表

Coding

/**
* 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; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null){
return head;
}
ListNode tem = head;
int len = 0;
while(tem != null){
tem = tem.next;
len++;
}
k = k % len;
ListNode slow = head;
ListNode fast = head;
for(int i = 0;i < k;i++){
fast = fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
}
}