当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.203.Remove Linked List Elements

LeetCode.203.Remove Linked List Elements


题目描述

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两个指针,并且用了一个值无用的头结点,免得考虑链表为空的情况

class Solution {
    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;
    }
}

只用一个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代码


上一篇 LeetCode.028.Implement strStr()

下一篇 LeetCode.026.Remove Duplicates from Sorted Array

阅读
480
阅读预计2分钟
创建日期 2018-02-23
修改日期 2018-02-26
类别
百度推荐