203.移除链表元素
题目描述
删除链表中等于给定值 val
的所有节点。
示例 1:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解法一之遍历和哨兵节点
因为链表是通过指针连接的,所以我们只需要让需要删除的节点的上一个节点和下一个节点连接起来,这样链条上就删除了这个节点
举例 1->2->6->3->4->5
要删除值为 2
的节点。
- 应该先判断
1
的下一个节点是不是2
。 - 如果是就让
1
的指针指向下一个节点(需要删除的)的下一个节点1->2->6->3->4->5
=>1->6->3->4->5
。 - 如果不是就从下一个节点开始继续遍历。
哨兵节点
上面的逻辑有个问题,就是会跳过头节点的判断。因为一开始就是判断的当前节点(1)的下一个节点(2)。
所以解决方案就是让第一个节点变成第二个节点,临时定义一个新的头节点,称为哨兵节点。1->2->6->3->4->5
=> 0-1->2->6->3->4->5
。
最后在返回的时候去除哨兵节点即可。
代码实现
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
// 定义一个哨兵节点,便于遍历
let ele = {
next: head,
}
let cur = ele
while (cur.next) {
// 依次判断下一个节点的值是不是等于输入值
if (cur.next.val === val) {
// 让当前节点的指针指向下一个节点的下一个节点
cur.next = cur.next.next
} else {
cur = cur.next
}
}
return ele.next
}
// ===================================================================
// ========================== @test ==================================
// ===================================================================
let ListNode = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 2,
next: null,
},
},
},
}
function print(head) {
let cur = head
let link = []
while (cur) {
link.push(cur.val)
cur = cur.next
}
return `长度为 ${link.length} : 值为 ${link.join("->")}`
}
console.log(print(removeElements(ListNode, 2))) // 长度为 2 : 值为 1->3
本文参与
本文正在参与「掘金 2021 春招闯关活动」, 点击查看活动详情。
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!