LeetCode.203.Remove Linked List Elements 移除链表元素

题目描述

203 Remove Linked List Elements
https://leetcode-cn.com/problems/remove-linked-list-elements/
https://leetcode.com/problems/remove-linked-list-elements/description/

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

---

解题过程

删除链表中具有指定值的结点，非常简单的链表题，但如果多看看别人提交的代码的话，还是能学到些东西的。

使用cur和prev两个指针

我的代码如下，使用cur和prev两个指针，并且用了一个值无用的头结点，免得考虑链表为空的情况

private static class SolutionV2018 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode fakeHead = new ListNode(0);//值无用的头结点
        fakeHead.next = head;
        ListNode cur = fakeHead.next;
        ListNode prev = fakeHead;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        return fakeHead.next;
    }
}

时间复杂度 O(n)，空间复杂度 O(1)

只用一个cur指针

讨论区看到一个非常漂亮的代码，只用一个指针，一开始我也想怎么能只用一个指针，没想出来。总结了下：每次考察当前结点的话，还需要一个指针保留前一节点；每次考察后一结点的话，就只需要一个当前指针即可。

public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;
    ListNode pointer = head;
    while (pointer.next != null) {
        if (pointer.next.val == val) pointer.next = pointer.next.next;
        else pointer = pointer.next;
    }
    return head.val == val ? head.next : head;
}

这个代码妙的地方还在于，最后返回时才考察头结点的值，很简洁。

单指针版本的还可以如下这么写，加个头结点，看起来更易懂：

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;

    while(cur.next != null) {
        if(cur.next.val == val) {
            cur.next = cur.next.next;
        }
        else
            cur = cur.next;
    }
    return dummy.next;
}

递归法

和链表逆置一样，也有一个递归解法：

public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
}

---

GitHub代码

algorithms/leetcode/leetcode/_203_RemoveLinkedListElements.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_203_RemoveLinkedListElements.java

---