内容简介:删除链表中等于给定值示例:初始化一个哨兵节点
一、题目
删除链表中等于给定值 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; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- CSS 基础:块级元素、行内元素、替换元素、非替换元素
- CSS 技巧篇(六):display设置元素为行内元素时,元素之间存在间隙问题
- 探究行内元素和块级元素
- 重学前端:块级元素与内联元素
- 使CSS伪元素:在与主元素相同的高度之前
- 求非负元素数组所有元素能组合的最大字符串
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
A=B
Marko Petkovsek、Herbert S. Wilf、Doron Zeilberger / AK Peters, Ltd. / 1996-01 / USD 49.00
At some point, this book describes methods of solving the problem raised by Donald E. Knuth in the classical book "The Art of Computer Programming, Volume 1: Fundamental Algorithms". The main purpo......一起来看看 《A=B》 这本书的介绍吧!