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 实现的代码：

// 省略了 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); } }

运行结果

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

Original list: 1 2 3 4 5 Rotated list by 2 positions: 4 5 1 2 3

总结

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

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

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

问题描述

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

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

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

解决方案

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

以下是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初始化柱子A for (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方法来解决汉诺塔问题，并打印出最终的结果。

 

结论

通过使用栈来模拟递归过程，我们不仅解决了汉诺塔问题，而且更深入地理解了递归和栈的工作原理。这种方法在实际编程中非常有用，特别是在处理需要模拟递归过程或需要使用后进先出数据结构的问题时。希望这篇博客能够帮助你更好地理解汉诺塔问题和栈的使用！