携手创作,共同生长!这是我参与「日新计划 8 月更文挑战」的第22天,点击检查活动详情

标题

请编写一个函数,用于 删去单链表中某个特定节点。在设计函数时需求注意,你无法拜访链表的头节点head,只能直接拜访 要被删去的节点

标题数据保证需求删去的节点 不是结尾节点

示例 1:

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

示例 2:

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

方法一:和下一个节点交流

思路及解法

删去链表中的节点的常见的方法是定位到待删去节点的上一个节点,修正上一个节点的 next\textit{next} 指针,使其指向待删去节点的下一个节点,即可完结删去操作。

这道题中,传入的参数 node\textit{node} 为要被删去的节点,无法定位到该节点的上一个节点。注意到要被删去的节点不是链表的结尾节点,因而 node.next\textit{node}.\textit{next} 不为空,能够经过对 node\textit{node} 和 $textit{node}.\textit{next}$ 进行操作实现删去节点。

在给定节点 node\textit{node} 的情况下,能够经过修正 node\textit{node}next\textit{next} 指针的指向,删去 node\textit{node} 的下一个节点。可是标题要求删去 node\textit{node},为了到达删去 node\textit{node} 的作用,只要在删去节点之前,将 node\textit{node} 的节点值修正为 node.next\textit{node}.\textit{next} 的节点值即可。

例如,给定链表 4→5→1→94 \rightarrow 5 \rightarrow 1 \rightarrow 9,要被删去的节点是 55,即链表中的第 22 个节点。能够经过如下两步操作实现删去节点的操作。

将第 22 个节点的值修正为第 33 个节点的值,行将节点 55 的值修正为 11,此刻链表如下:
4→1→1→94 \rightarrow 1 \rightarrow 1 \rightarrow 9

删去第 33 个节点,此刻链表如下:
4→1→94 \rightarrow 1 \rightarrow 9

到达删去节点 55 的作用。

代码

class Solution {
    func deleteNode(_ node: ListNode?) {
        node?.val = node?.next?.val ?? 0
        node?.next = node?.next?.next
    }
}

复杂度分析

  • 时间复杂度:O(1)O(1)

  • 空间复杂度:O(1)O(1)