链表，是谁动了我的奶酪

题目描述

删除链表中等于给定值 val 的所有节点。
LeetCode

示例

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
LeetCode

思路分析

为了方便演示，将题目示例给出的列表简化为如下图所示：

定义一个虚拟头结点dummyHead，然后其下一个结点为head。

定义变量prev，指向虚拟头结点dummyHead。

题目要求移除链表中值为val=6的结点，因此先看变量prev指向的结点的下一个结点的值是不是与val的值相等。

这里prev.next.val=1与给定值val=6不相等。

因此，变量prev向前移动一个位置，即虚拟头结点dummyHead之后的结点与变量prev指向的结点及其之前的结点都是需要保留的结点。在这里结点1就是需要保留的结点。

接着看变量prev所指向的结点的后继结点值是否与给定值val=6相等。在这里prev.next.val=2与给定值不相等。

因此变量prev继续向前移动一个位置，这时结点1和结点2都是需要保留的结点。

继续看变量prev所指向结点的后继结点，这时其后继结点prev.next.val=6与给定的值val=6相等。因此，需要将其后继结点删除。

要删除变量prev所指向的结点的后继结点6，需要将结点6的后继结点挂在变量prev所指向的结点之后，即下图中的结点3要挂在结点2之后。

要想将结点3挂在变量prev指向的结点2之后，需要执行prev.next=prev.next.next，如下图所示。

这时，就将值为6的结点从链表中移除了，此时链表的结构如下：

接着，要做的就是看变量prev指向的结点的后继结点的值val是否与给定的val=6相等。在这里，prev.next.val=3与给定值val=6不相等。

接着将变量prev继续向后移动一个位置。此时，prev.next=null，因此到这里就将链表中值等于6的结点移除了。

然后返回dummyHead.next，就是最终结果了。

动画演示

代码实现

图片查看

public ListNode removeElements1(ListNode head, int val) {    ListNode dummyHead = new ListNode(0);    dummyHead.next = head;
    ListNode prev = dummyHead;    // 判断当前结点的后继结点是否为null    while (prev.next != null) {        // 如果当前结点的后继结点的值与给定值val相等        // 则需将其后继结点删除        if (prev.next.val == val) {            // 通过将当前结点后继结点的后继结点挂在当前结点之后            // 来删除当前结点的后继结点            prev.next = prev.next.next;        } else {            // 如果当前结点的后继结点的值与给定值不相等            // 则当前结点需要保留，因此prev向前移动一个位置            prev = prev.next;        }    }    return dummyHead.next;}

一个问题：为什么最后返回时返回的是dummyHead.next而不是head?

假设现在链表中只有一个结点1，那么它的结构是1—>null。

加上虚拟头结点dummyHead时结构是0—>1—>null。

假设现在移除1这个结点，那么在移除1这个结点后链表其实变为了两部分：

一部分是变量dummyHead指向的，即0—>null
另一部分是变量head指向的即1—>null

这时返回dummyHead.next，即返回的结果是null，是移除结点1后的结果。而如果返回head则返回的结果是1—>null，结点1还存在，因为head这个变量一直指向的都是1这个结点。

所以最后返回的是dummyHead.next

更多相关文章

随机推荐