理解链表的append操作
在单向链表中实现append（追加）操作，其目标是将一个链表（源链表）的所有元素连接到另一个链表（目标链表）的末尾。例如，如果目标链表为 [0, 1, 2]，源链表为 ['a', 'b']，那么append操作后的结果应为 [0, 1, 2, 'a', 'b']。
初学者常犯的一个错误是尝试直接将目标链表的 head.next 指向源链表的 head。这种做法是错误的，因为它只会将源链表的头部连接到目标链表的第二个节点之后，而丢弃了目标链表剩余的部分。正确的做法是找到目标链表的最后一个节点，然后将这个节点的 next 指针指向源链表的头节点。
append方法实现思路
实现append方法需要遵循以下步骤：
- 处理目标链表为空的情况： 如果要追加的目标链表（即调用append方法的链表this）是空的，那么追加操作的结果就是源链表本身。此时，只需将目标链表的 head 指向源链表的 head。
- 处理源链表为空的情况： 如果要追加的源链表（即传入append方法的list）是空的，那么追加操作不会改变目标链表，可以直接返回。
- 遍历目标链表： 从目标链表的 head 开始，一直遍历到链表的最后一个节点。最后一个节点的特征是其 next 指针为 null。
- 连接链表： 找到目标链表的最后一个节点后，将其 next 指针指向源链表的 head。
Java代码示例
下面是一个完整的Java单向链表实现，包含了append方法以及辅助的add和printList方法。
public class LinkedList {
private Node head; // 链表的头节点
// 内部类，表示链表中的一个节点
private static class Node {
int data; // 节点存储的数据
Node next; // 指向下一个节点的引用
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 向链表末尾添加元素的方法
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// 打印链表所有元素的方法
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
/**
* 将另一个链表追加到当前链表的末尾。
*
* @param otherList 要追加到当前链表末尾的链表。
*/
public void append(LinkedList otherList) {
// 1. 处理源链表为空的情况
if (otherList == null || otherList.head == null) {
// 如果otherList为空或otherList没有元素，则无需追加，直接返回
return;
}
// 2. 处理当前链表（this）为空的情况
if (this.head == null) {
// 如果当前链表为空，则直接将otherList作为当前链表
this.head = otherList.head;
return;
}
// 3. 遍历当前链表，找到最后一个节点
Node current = this.head;
while (current.next != null) {
current = current.next;
}
// 4. 将当前链表的最后一个节点的next指针指向otherList的头节点
current.next = otherList.head;
}
public static void main(String[] args) {
// 创建第一个链表
LinkedList list1 = new LinkedList();
list1.add(0);
list1.add(1);
list1.add(2);
System.out.print("List1: ");
list1.printList(); // 输出: List1: 0 -> 1 -> 2 -> null
// 创建第二个链表
LinkedList list2 = new LinkedList();
list2.add(10);
list2.add(11);
System.out.print("List2: ");
list2.printList(); // 输出: List2: 10 -> 11 -> null
// 将list2追加到list1的末尾
list1.append(list2);
System.out.print("List1 after appending List2: ");
list1.printList(); // 输出: List1 after appending List2: 0 -> 1 -> 2 -> 10 -> 11 -> null
// 测试当前链表为空的情况
LinkedList emptyList = new LinkedList();
LinkedList singleNodeList = new LinkedList();
singleNodeList.add(99);
System.out.print("EmptyList: ");
emptyList.printList();
System.out.print("SingleNodeList: ");
singleNodeList.printList();
emptyList.append(singleNodeList);
System.out.print("EmptyList after appending SingleNodeList: ");
emptyList.printList(); // 输出: EmptyList after appending SingleNodeList: 99 -> null
// 测试源链表为空的情况
LinkedList list3 = new LinkedList();
list3.add(100);
LinkedList emptyOtherList = new LinkedList();
System.out.print("List3: ");
list3.printList();
System.out.print("EmptyOtherList: ");
emptyOtherList.printList();
list3.append(emptyOtherList);
System.out.print("List3 after appending EmptyOtherList: ");
list3.printList(); // 输出: List3 after appending EmptyOtherList: 100 -> null
}
}代码解析
- Node 内部类： 定义了链表节点的基本结构，包含数据 (data) 和指向下一个节点的引用 (next)。
- head 成员变量： LinkedList 类通过 head 节点来标识链表的起点。
- add(int data) 方法： 这是一个辅助方法，用于向链表末尾添加新元素，方便测试。
- printList() 方法： 另一个辅助方法，用于遍历并打印链表中的所有元素。
-
append(LinkedList otherList) 方法：
- 首先检查 otherList 是否为空或不包含任何节点。如果是，则直接返回，因为没有内容可以追加。
- 接着检查当前链表 (this.head) 是否为空。如果当前链表为空，则意味着它本身没有节点，此时追加 otherList 的结果就是 otherList 本身，因此直接将 this.head 指向 otherList.head。
- 如果两个链表都非空，则通过 while (current.next != null) 循环遍历当前链表，直到 current 指向最后一个节点（即 current.next 为 null）。
- 最后，将找到的最后一个节点的 next 指针指向 otherList.head，完成了两个链表的连接。
注意事项
- 方法位置： append 方法应该作为 LinkedList 类的一个成员方法，而不是 Node 类的方法。因为 append 操作是针对整个链表结构进行的，需要访问链表的 head。
- 空链表处理： 务必处理好当前链表为空和要追加的链表为空这两种边界情况，否则可能导致 NullPointerException 或逻辑错误。
- 源链表状态： append 操作完成后，源链表（otherList）的节点实际上被合并到了目标链表。如果之后对 otherList 进行修改（例如添加或删除元素），这些修改也会影响到追加后的目标链表，因为它们共享相同的节点。在某些场景下，可能需要进行深拷贝以避免这种副作用。
- 时间复杂度： append 方法的时间复杂度为 O(N)，其中 N 是目标链表的长度，因为需要遍历目标链表以找到其尾节点。
- 内存管理： 在Java中，由于有垃圾回收机制，通常不需要手动管理节点的内存释放。
总结
正确实现单向链表的 append 方法，关键在于准确找到目标链表的尾节点，并将其 next 指针指向源链表的头节点。同时，充分考虑并妥善处理空链表的边界条件，是编写健壮代码的重要一环。通过本文提供的实现思路和代码示例，读者可以清晰地理解并掌握这一核心链表操作。
立即学习“Java免费学习笔记（深入）”；
