Java每日精进·45天挑战·Day20

第二部分：链表旋转

在数据结构中，链表是一种非常基础且重要的数据结构。它允许我们在不需要大量数据移动的情况下，在任意位置插入或删除元素。今天，我们将探讨一个链表相关的有趣问题：如何将链表向右旋转 k 个位置？

问题描述

给定一个链表的头节点 head 和一个整数 k，你需要将链表向右旋转 k 个位置。即，将链表中的每个节点向右移动 k 个位置，如果链表长度为 n，则移动 n 次后将回到原始链表。

例如，对于输入 head = [1,2,3,4,5] 和 k = 2，输出应为 [4,5,1,2,3]。

解决思路

为了解决这个问题，我们可以采取以下步骤：

计算链表长度：
首先，我们需要遍历链表一次，以计算链表的长度 n。
调整 k 的值：
由于旋转 n 次链表会回到原始状态，因此我们可以将 k 对 n 取模，即 k = k % n。如果 k == 0，则链表不需要旋转。
找到新的头节点和尾节点：
我们需要遍历链表，找到倒数第 k 个节点，这个节点将成为新的头节点。同时，我们需要记录最后一个节点，以便将其 next 指针指向原始链表的头节点，从而形成环状链表。
形成环状链表并断开：
将原始链表的尾节点的 next 指针指向头节点，形成环状链表。然后，找到倒数第 k+1 个节点，并将其 next 指针置为 null，以断开环状链表，得到新的链表。

Java 实现

以下是 Java 实现的代码：

java">// 省略了 ListNode 类的定义，与上文相同public class RotateList {public ListNode rotateRight(ListNode head, int k) {// 省略了具体实现，与上文相同}// 省略了 printList 方法，用于打印链表（测试用）public static void main(String[] args) {RotateList solution = new RotateList();// 创建一个链表进行测试// 省略了链表的创建代码，与上文相同int k = 2;// 打印原始链表System.out.println("Original list:");solution.printList(head);// 旋转链表ListNode rotatedHead = solution.rotateRight(head, k);// 打印旋转后的链表System.out.println("Rotated list by " + k + " positions:");solution.printList(rotatedHead);}
}

运行结果

运行上述代码，你将得到以下输出：

java">Original list:
1 2 3 4 5 
Rotated list by 2 positions:
4 5 1 2 3

总结

链表旋转是一个有趣且实用的链表操作问题。通过计算链表长度、调整 k 的值、找到新的头节点和尾节点，并形成环状链表再断开，我们可以轻松地解决这个问题。希望这篇文章能帮助你更好地理解链表旋转的实现过程，并在实际编程中灵活运用。

第二部分：解决汉诺塔问题

汉诺塔问题是一个经典的递归问题，它要求我们将一系列不同大小的盘子从一个柱子移动到另一个柱子，同时遵守特定的规则。通常，我们会使用递归算法来解决这个问题。但是，今天我们将采用一种不同的方法：使用栈来模拟递归过程。这种方法不仅能够帮助我们更好地理解递归的本质，而且在实际编程中也非常有用。

问题描述

在汉诺塔问题中，有三根柱子和N个不同大小的穿孔圆盘。盘子可以滑入任意一根柱子，但移动时受到以下限制：

每次只能移动一个盘子。
盘子只能从柱子顶端滑出移到下一根柱子。
盘子只能叠在比它大的盘子上。

目标是将所有盘子从第一根柱子（源柱子）移动到最后一根柱子（目标柱子）。

解决方案

我们将使用三个栈来分别代表三根柱子：源柱子（source）、辅助柱子（auxiliary）和目标柱子（target）。栈的特点是后进先出（LIFO），这恰好可以模拟汉诺塔问题中盘子的移动规则。

以下是Java代码的实现：

java">import java.util.Stack;public class HanoiTower {// 定义一个方法来解决汉诺塔问题public void solveHanoi(Stack<Integer> source, Stack<Integer> auxiliary, Stack<Integer> target, int n) {// 定义一个辅助方法，用于将n个盘子从source柱通过auxiliary柱移动到target柱solveHanoiHelper(source, auxiliary, target, n);}// 辅助方法，用于递归解决汉诺塔问题private void solveHanoiHelper(Stack<Integer> source, Stack<Integer> auxiliary, Stack<Integer> target, int n) {if (n == 0) {// 递归基，当没有盘子需要移动时，直接返回return;}// 将n-1个盘子从source柱通过target柱移动到auxiliary柱solveHanoiHelper(source, target, auxiliary, n - 1);// 将第n个盘子（即最大的盘子）从source柱移动到target柱int topDisk = source.pop();target.push(topDisk);// 将n-1个盘子从auxiliary柱通过source柱移动到target柱solveHanoiHelper(auxiliary, source, target, n - 1);}// 为了展示结果，我们可以定义一个打印栈的方法public void printStacks(Stack<Integer> A, Stack<Integer> B, Stack<Integer> C) {System.out.print("A = [");for (int disk : A) {System.out.print(disk + " ");}System.out.print("], ");System.out.print("B = [");for (int disk : B) {System.out.print(disk + " ");}System.out.print("], ");System.out.print("C = [");for (int disk : C) {System.out.print(disk + " ");}System.out.println("]");}public static void main(String[] args) {HanoiTower hanoi = new HanoiTower();// 初始化三个栈，分别代表三根柱子Stack<Integer> A = new Stack<>();Stack<Integer> B = new Stack<>();Stack<Integer> C = new Stack<>();// 根据示例1初始化柱子Afor (int i = 2; i >= 0; i--) {A.push(i);}// 打印初始状态hanoi.printStacks(A, B, C);// 解决汉诺塔问题hanoi.solveHanoi(A, B, C, A.size());// 打印最终状态hanoi.printStacks(A, B, C);// 根据示例2，可以重新初始化柱子A并再次运行程序来验证// ...（省略示例2的初始化代码，与示例1类似）}
}

代码解释

类定义：我们定义了一个HanoiTower类来封装解决问题的方法。
solveHanoi方法：这是公开的接口方法，用于启动解决汉诺塔问题的过程。它接受四个参数：源柱子、辅助柱子、目标柱子和盘子的数量。
solveHanoiHelper方法：这是一个私有的辅助方法，用于递归地解决汉诺塔问题。它遵循汉诺塔问题的规则，通过递归调用自身来移动盘子。
printStacks方法：为了展示结果，我们定义了一个打印栈的方法。它接受三个栈作为参数，并按照从栈底到栈顶的顺序打印出每个栈中的盘子。
main方法：在main方法中，我们初始化了三个栈来代表三根柱子，并根据示例初始化了源柱子。然后，我们调用solveHanoi方法来解决汉诺塔问题，并打印出最终的结果。