leetcode剑指 Offer 18. 删除链表的节点

leetcode 剑指 Offer 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.

说明：

题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

顺序查找删除:\

1. 找到值为value的节点
   索引for循环遍历链表的每一个节点找到node.value==value的节点
2. 删除它
   我们使用隔离法从链表在移除此节点,就是它前一个的next节点之间等于它下一个节点,这样这个节点就从链表中移除了\

• 时间复杂度(O(n))
• 空间复杂度(O(1)),我们只需要申请一个q(node)去储存节点的前一个节点就可以实现了

执行结果

法1

func deleteNode(head *ListNode, val int) *ListNode {
 if head.Val == val {
  return head.Next
 }
 p := head
 for p.Next != nil {//寻找值为val的节点
  if p.Next.Val == val { //删除元素
   p.Next = p.Next.Next
   return head
  }
  p = p.Next
 }
 p = nil
 return head
}

行用时： 4 ms , 在所有 Go 提交中击败了 60.53% 的用户 内存消耗： 2.7 MB , 在所有 Go 提交中击败了 62.02% 的用户 通过测试用例： 37 / 37 炫耀一下:

进阶

如果链表中存在相同元素呢?
我们就不能找的一个相同的value就删除后返回结果了,我们需要将整个链表遍历完,找出所有node.value==value的节点并删除它

func deleteNode2(head *ListNode, val int) *ListNode {
 if head.Val == val {
  head = head.Next
 }
 p := head
 for p.Next != nil { //寻找值为val的节点
  if p.Next.Val == val { //删除元素
   p.Next = p.Next.Next
  }
  p = p.Next
 }
 if p.Val == val {
  p = nil
 }
 return head
}