当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.203.Remove Linked List Elements 移除链表元素

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


上一篇 LeetCode.028.Implement strStr()

下一篇 LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项

阅读
评论
514
阅读预计2分钟
创建日期 2018-02-23
修改日期 2020-02-18
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论