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

栏目: IT技术 · 发布时间: 4年前

内容简介:删除链表中等于给定值示例:初始化一个哨兵节点

一、题目

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

示例:

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

二、题解

  • 解法1:哨兵节点。

初始化一个哨兵节点 solider ,并将其 next 指针指向链表的头部;

初始化一个指针 prev 指向哨兵节点 solider ,作为前继节点;

比较前继节点的下一个节点和要删除的节点,若下一个节点是要删除的节点,则 prev->next = prev->prev->next ,反之则前继节点移动到下一个节点,即 prev = prev->next

最后返回 solider->next

时间复杂度:O(n);空间复杂度:O(1)。

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) { 
        $this->val = $val; 
    }
}

/**
 * @param ListNode $head
 * @param Integer $val
 * @return ListNode
 */
function removeElements($head, $val) {
    $solider = new ListNode(null);
    $solider->next = $head;

    $prev = $solider;
    while ($prev->next!= null) {
        if ($prev->next->val == $val) {
            $prev->next = $prev->next->next;
        } else {
            $prev = $prev->next;
        }
    }

    return $solider->next;
}
  • 解法2:不设置哨兵节点(虚拟头节点)

上面的解法是设置了一个虚拟头节点,那如果不设置虚拟头节点呢?

先判断链表的头节点是不是要删除的值,如果是,则将头节点向后移动,若移动完后头节点为空,则说明该链表的所有节点均为要删除的;

设置一个前继节点 prev ,并指向头节点,比较前继节点的下一个节点的值和要删除的值,若相等,则将前继节点的下一个节点指向前继节点下一个节点的下一个节点,反之则前继节点向后移动;

最后返回 head 即可。

function removeElements($head, $val) {
    //如果开头就是要删的元素,则将头节点移动
    while ($head->val == $val) {
        $head = $head->next;
    }

    //如果链表全是要删除的元素,则头节点经过上述操作后为空
    if ($head == null) {
        return null;
    }

    $prev = $head;
    while ($prev->next!= null) {
        if ($prev->next->val == $val) {
            $prev->next = $prev->next->next;
        } else {
            $prev = $prev->next;
        }
    }

    return $head;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

闪魂FLASH8网站建设实录

闪魂FLASH8网站建设实录

马谧铤 / 中国林业 / 2006-7 / 46.00元

《闪魂FLASH8网站建设实录》旨在提供以Flash(Flash 8.0为创作工具)为技术核心的整套互动网站的开发思路,其中包括了网站策划、平面设计、程序设计等实用的互联网应用技术。内容包括Photoshop CS2设计,FIash 8创作和ActionScript应用程序开发的操作流程。在技术学习的过程中.大家还将体会到顶级互动网站设计、网站建设的设计流程和思路。《闪魂FLASH8网站建设实录》......一起来看看 《闪魂FLASH8网站建设实录》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

html转js在线工具
html转js在线工具

html转js在线工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具