今天我们将深入探讨Java编程中的一个重要面试题解——《剑指 Offer》系列的第11天内容。本节主要讨论的是如何在链表中删除特定值的节点。题目给出的示例是编写一个名为`DeleteNode`的类，用于删除链表中值为`val`的第二个节点。让我们详细解析这段代码并理解其实现原理。
首先，定义了一个`ListNode`类，它包含两个属性：`val`表示节点的值，`next`是一个指向下一个节点的引用。`ListNode`构造方法接受一个整数`x`作为参数，初始化节点的值。
在`DeleteNode`类中，有一个名为`deleteNode`的方法，接收两个参数：一个`ListNode`类型的头节点`head`和一个整数`val`。这个方法的主要目标是遍历链表，找到值为`val`的第二个节点，并将其从链表中移除。
1. **头节点判断**：
如果头节点的值恰好是`val`，那么直接返回`head.next`，这样就将头节点删除了。这是因为我们要删除第二个`val`节点，而头节点可能本身就是需要删除的那个。
2. **遍历链表**：
使用两个指针`pre`和`cur`，其中`pre`初始时指向头节点，`cur`指向`head.next`。当`cur`不为空且值不等于`val`时，继续遍历。这样做是为了找到第一个`val`节点（即第二个需要删除的节点）。
3. **删除节点**：
当`cur`为`null`或者`cur.val`等于`val`时，说明找到了需要删除的节点。此时，通过`pre.next = cur.next`将`pre`的下一个节点设置为`cur.next`，实际上就将`cur`节点从链表中移除了。`pre`和`cur`的关系确保了我们不会改变其他节点的链接。
4. **返回结果**：
在循环结束后，如果链表未被修改，即`cur`仍然不为`null`，那么`head`就是新的头节点，因为它没有被替换。最后，返回`head`作为处理后的链表的头节点。
接下来，问题描述提到了另一个未完成的功能，即找到链表中倒数第k个节点。这个任务通常会涉及到对链表的遍历和动态数组（如`ArrayList`）的辅助存储，以便在遇到目标位置时可以快速访问。实现方式可能包括维护一个大小为`k`的队列，每次将当前节点入队，当队列满时出队头元素，直到队列只剩最后一个元素，此时队首的就是倒数第k个节点。
总结来说，这部分内容主要考察了链表操作的基本技巧，包括节点的查找、删除以及对链表遍历的理解。在实际面试中，这类问题有助于测试候选人的数据结构和算法知识，特别是对于处理动态数据结构的能力。
我的内容管理
展开
