LeetCode#203-Remove Linked List Elements-移除链表元素
鹿呦呦 人气:0一、题目
删除链表中等于给定值 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;
}
加载全部内容