【链表】Leetcode 61. 旋转链表【中等】

本文主要是介绍【链表】Leetcode 61. 旋转链表【中等】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

旋转链表

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

示例 1：

在这里插入图片描述
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

解题思路

要将链表每个节点向右移动 k 个位置：

计算链表长度：首先遍历链表以获取其长度 n。
计算有效移动次数：因为旋转长度超过链表长度时会回到原点，所以有效的移动次数为 k % n。
找到新的链表头和尾：
新的链表尾在从头开始的第 (n - k % n - 1) 个节点。
新的链表头在从头开始的第 (n - k % n) 个节点。
断开并连接链表：将新尾节点的 next 指针设为 null，将旧的尾节点的 next 指向旧的头节点，形成一个新的链表。

Java实现

public class RotateRightLinked {public static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null || k == 0) {return head;}// 计算链表长度ListNode oldTail = head;int n = 1;while (oldTail.next != null) {oldTail = oldTail.next;n++;}// 计算有效的移动次数k = k % n;if (k == 0) {return head;}// 找到新的尾节点和新的头节点ListNode newTail = head;for (int i = 0; i < n - k - 1; i++) {newTail = newTail.next;}ListNode newHead = newTail.next;// 断开链表并连接newTail.next = null;oldTail.next = head;return newHead;}public static void main(String[] args) {RotateRightLinked rotateRightLinked = new RotateRightLinked();// 创建示例链表 1->2->3->4->5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 旋转链表ListNode newHead = rotateRightLinked.rotateRight(head, 2);printList(newHead); // 输出: 4->5->1->2->3}// 辅助方法：打印链表public static void printList(ListNode head) {ListNode current = head;while (current != null) {System.out.print(current.val);if (current.next != null) {System.out.print("->");}current = current.next;}System.out.println();}
}