LeetCode203-移除链表元素

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/remove-linked-list-elements/

中文链接：https://leetcode-cn.com/problems/remove-linked-list-elements/

题目详述

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

示例:

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

题目详解

本题是删除链表中等于给定值的所有结点，LeetCode237-删除链表中的结点 则是删除指定结点，可以借用 LeetCode237 中的思想来删除结点，只不过到达尾结点的时候要特殊处理一下。由于本题可以知道待删除结点的前一个结点，采用删除结点的常用方法即可。为了方便操作，可以新建一个结点，让它成为头结点。当然，也可以不新建结点。

下面是新建一个头结点版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class LeetCode_00203 {

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
        }
        return dummy.next;
    }
}

下面是不新建结点版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class LeetCode_00203 {

    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {   // 找到第一个值不等于 val 的非空结点
            head = head.next;
        }
        if (head == null) {                         // 不满足直接返回 null
            return null;
        }
        ListNode cur = head.next;
        ListNode pre = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}