删除链表的节点

18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为  5  的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为  1  的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

代码

思路：快慢指针

创建虚拟头节点 dummyNode
声明快慢指针
- slow = dummyNode
- fast = dummyNode
找到需要删除节点的上一个节点
- while 循环
  - 终止条件:while(fast)
  - 查询逻辑放到快慢指针中间
  - 存在：
    - 将上一个节点的 next 指向下一个节点，来删除当前节点
    - 打断循环
返回删除后虚拟头节点

const head = {
  'val':1,
  'next':{
    'val':2,
    'next':{
      'val':3,
      'next':{
        'val':4,
        'next':undefined
      }
    }
  }
}

class ListNode{
  constructor(val,next){
    this.val = val;
    this.next = next || null;
  }
}

var deleteNode = function(head, val) {
  let dummyNode = new ListNode(-1,head)

  let slow = dummyNode
  let fast = dummyNode

  while(fast){
    fast = fast.next

    if(fast && fast.val === val){
      slow.next = slow.next.next
      break
    }

   slow = slow.next
  }
  return dummyNode.next
}

console.log(deleteNode(head,2))

18. 删除链表的节点​

代码​

18. 删除链表的节点

代码