leetcode原题链接：剑指 Offer 18. 删除链表的节点
删除值为 val 的节点分需为两步：定位节点、修改引用。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head: return head
if head.val == val:
return head.next
pre, cur = head.next, head
while pre:
if pre.val == val:
cur.next = pre.next
return head
pre, cur = pre.next, cur.next
return head
复杂度分析
时间复杂度
O
(
N
)
O(N)
O(N) ：
N
N
N为链表长度，删除操作平均需循环
N
/
2
N/2
N/2 次，最差
N
N
N 次。
空间复杂度
O
(
1
)
O(1)
O(1) ： cur, pre 占用常数大小额外空间。