链表、栈和队列的深入解析与应用

# 链表、栈和队列的深入解析与应用 ## 1. 合并两个有序链表 ### 1.1 问题描述 在之前，我们讨论过合并两个有序数组的问题，现在我们将探讨如何合并两个以链表形式存储的有序列表，以生成一个新的有序链表。 ### 1.2 算法思路 合并两个有序链表的算法如下： ```plaintext while (A 和 B 中至少还有一个数字) { if (A 中的最小数字 < B 中的最小数字) { 将 A 中的最小数字添加到 C 移动到 A 中的下一个数字 } else { 将 B 中的最小数字添加到 C 移动到 B 中的下一个数字 } } // 此时，至少有一个列表已经结束 while (A 还有数字) { 将 A 中的最小数字添加到 C 移动到 A 中的下一个数字 } while (B 还有数字) { 将 B 中的最小数字添加到 C 移动到 B 中的下一个数字 } ``` ### 1.3 代码实现 以下是在 `LinkedList` 类中实现的 `merge` 方法： ```java public LinkedList merge(LinkedList LL) { Node A = this.head; Node B = LL.head; LinkedList C = new LinkedList(); while (A != null && B != null) { if (A.data.compareTo(B.data) < 0) { C.addTail(A.data); A = A.next; } else { C.addTail(B.data); B = B.next; } } while (A != null) { C.addTail(A.data); A = A.next; } while (B != null) { C.addTail(B.data); B = B.next; } return C; } //end merge ``` ### 1.4 优化方案 当前的 `addTail` 方法在添加每个新节点之前需要遍历整个列表以找到末尾，效率较低。我们可以使用 `addHead` 方法添加新节点，在合并完成后反转列表。修改后的 `merge` 方法如下： ```java public LinkedList merge(LinkedList LL) { Node A = this.head; Node B = LL.head; LinkedList C = new LinkedList(); while (A != null && B != null) { if (A.data.compareTo(B.data) < 0) { C.addHead(A.data); A = A.next; } else { C.addHead(B.data); B = B.next; } } while (A != null) { C.addHead(A.data); A = A.next; } while (B != null) { C.addHead(B.data); B = B.next; } C.reverseList(); return C; } ``` ### 1.5 测试程序 以下是用于测试 `merge` 方法的程序 `MergeLists.java`： ```java import java.util.*; public class MergeLists { public static void main(String[] args) { Scanner in = new Scanner(System.in); LinkedList A = createSortedList(in); LinkedList B = createSortedList(in); System.out.printf("\nWhen we merge\n"); A.printList(); System.out.printf("with\n"); B.printList(); System.out.printf("we get\n"); A.merge(B).printList(); } //end main public static LinkedList createSortedList(Scanner in) { LinkedList LL = new LinkedList(); System.out.printf("Enter some integers ending with 0\n"); int n = in.nextInt(); while (n != 0) { LL.addInPlace(new NodeData(n)); n = in.nextInt(); } return LL; } //end createSortedList } //end MergeLists ``` 示例运行结果： ```plaintext Enter some integers ending with 0 8 4 12 6 10 2 0 Enter some integers ending with 0 5 7 15 1 3 0 When we merge 2 4 6 8 10 12 with 1 3 5 7 15 we get 1 2 3 4 5 6 7 8 10 12 15 ``` ## 2. 循环链表和双向链表 ### 2.1 循环链表 #### 2.1.1 特点 在循环链表中，最后一个节点指向第一个节点，因此没有空指针来指示列表的结束。在遍历循环链表时，需要特别注意避免陷入无限循环。 #### 2.1.2 遍历方法 为了避免无限循环，我们可以保存起始节点的指针，并在回到该节点时停止遍历。示例代码如下： ```java Node curr = top; do { // 对 curr 指向的节点执行操作 curr = curr.next; } while (curr != top); ``` 需要注意的是，在进入循环之前，要确保列表不为空，以避免解引用空指针。 #### 2.1.3 应用场景 循环链表适用于表示循环的场景，例如纸牌或棋盘游戏中玩家的轮流顺序，以及儿童游戏“报数出局”。 #### 2.1.4 报数出局游戏 以下是使用循环链表解决报数出局游戏的程序 `CountOut.java`： ```java import java.util.*; public class CountOut { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m, n; do { System.out.printf("Enter number of children and length of count-out: "); n = in.nextInt(); m = in.nextInt(); } while (n < 1 || m < 1); Node last = linkCircular(n); //link children in a circular list Node winner = playGame(last, n-1, m); //eliminate n-1 children System.out.printf("The winning child: %d\n", winner.num); } //end main public static Node linkCircular(int n) { //link n children in a circular list; //return pointer to last child; this will point to the first Node first, np; first = np = new Node(1); //first child for (int h = 2; h <= n; h++) { //link the others np.next = new Node(h); np = np.next; } np.next = first; //set last child to point to first return np; } //end linkCircular public static Node playGame(Node last, int x, int m) { //Eliminate x children with countout length of m; //last points to the last child which points to the first child Node prev = last, curr = last.next; //curr points to first child //eliminate x children for (int h = 1; h <= x; h++) { //curr is pointing at the first child to be counted; //count m-1 more to get to the mth child for (int c = 1; c < m; c++) { prev = curr; curr = curr.next; } //delete the mth child prev.next = curr.next; curr = prev.next; //set curr to the child after the one eli ```