18-删除链表的节点

题目

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

思路

if head.next.val = val:
head.next = head.next.next

时间复杂度是：O(n)

# 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 head.val == val:
            return head.next
        cur = head
        while cur:
            # print(cur.val)
            if cur.next.val == val:
                cur.next = cur.next.next
                break
            else:
                cur = cur.next
        return head

改进一下，增加一个空节点

# 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 head.val == val:
            return head.next
        nullptr = ListNode(0)
        nullptr.next = head
        while nullptr:
            # print(cur.val)
            if nullptr.next.val == val:
                nullptr.next = nullptr.next.next
                break
            else:
                nullptr = nullptr.next
        return head

扩展

如何在O(1)的时间复杂度内删除链表中的某个节点？

删除节点i：

• 先把i的下一个节点j的内容复制到i；
• i的指针指向节点j的下一个节点
• 删除节点j。

至此，就完成删除操作。

如果位于链表尾部，没有下一个节点，仍然需要从链表节点开始顺序遍历。

如果只有一个节点，那么把链表的头节点设置为nullptr(Null pointer)。