剑指offer 面试题18. 在O(1)时间内删除链表的节点

考查应聘者的创新思维能力。这道题要求应聘者打破常规的思维模式。

Tag

链表

考点

  • 考查应聘者对链表的编程能力。
  • 考查应聘者的创新思维能力。这道题要求应聘者打破常规的思维模式。当我们想删除一个节点时，并不一定要删除这个节点本身。可以先把下一个节点的内容复制出来覆盖被删除节点的内容，然后把下一个节点删除。这种思路不是很容易想到的。
  • 考查应聘者思维的全面性。即使应聘者想到删除下一个节点这个办法，也未必能通过这轮面试。应聘者要全面考虑删除的节点位于链表的尾部及输入的链表只有一个节点这些特殊情况。

测试用例

  • 功能测试
  • 特殊测试：链表为空的情况、链表只有一个节点的情况、要删除的是尾节点，

Question

给定单向链表的头指针和一个节点指针，定义一个函数在 \(O(1)\) 时间内删除该节点。链表节点与函数的定义如下：

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

Intuition

思路分析：

常规来说，要删除一个节点 node，就要找到其前驱节点 pre_node，然后通过 pre_node.next = pre_node.next.next 来删除，如图（b）所示。但是顺序寻找的时间复杂度为 \(O(n)\)，不满足条件。

这道题输入的就是一个节点指针，所以当我们要删除第 i 个节点时，由于已经有了第 i 个节点的节点指针，先把i 的下一个节点 j 的内容复制到i，然后把 i 的指针指向节点 j 的下一个节点。此时再删除节点 j，其效果刚好是把节点 i 删除了，如图（c）所示。

Snipaste_2020-05-06_10-47-58.png

特殊输入判定：

如果要删除的节点位于链表的尾部，那么它就没有下一个节点，怎么办？我们仍然从链表的头节点开始，顺序遍历得到该节点的前序节点，并按照图（b）的方法完成删除操作，这种特殊情况下时间复杂度为 \(O(n)\) 。 最后需要注意的是，如果链表中只有一个节点，而我们又要删除链表的头节点（也是尾节点），那么，此时我们在删除节点之后，还需要把链表的头节点设置为 nullptr。

复杂度分析：

分析这种思路的时间复杂度。对于 n-1 个非尾节点而言，我们可以在 \(O(1)\) 时间内把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；对于尾节点而言，由于仍然需要顺序查找，时间复杂度是 \(O(n)\) 。因此，总的平均时间复杂度是 \([(n-1) \times O(1)+O(n)]/n\)，结果还是 \(O(1)\) ，符合面试官的要求。

与面试官的讨论：

一般情况下，有关链表节点操作的问题，特殊判定时还要考虑节点不存在于该链表中的情况，但是由于本地要求在 \(O(1)\) 时间内删除节点，所以必须基于一个假设：要删除的节点的确在链表中。我们需要 \(O(n)\) 的时间才能判断链表中是否包含某一节点。受到 \(O(1)\) 时间的限制，我们不得不把确保节点在链表中的责任推给了函数的调用者。在面试的时候，我们可以和面试官讨论这个假设，这样面试官就会觉得我们考虑问题非常全面，同时也解释了为何不做链表判空。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution:
    def deleteNode(self, head, target_node):
        # 链表判空
        if head == None or target_node == None:
            return None

        # 表中有多个节点，且要删除的节点不是尾节点 O(1)。
        if target_node.next != None:
            target_node.val = target_node.next.val
            target_node.next = target_node.next.next

        # 链表只有一个节点 O(1)
        elif head == target_node:
            return None

        # 链表中有多个节点，且删除尾节点 O(n)。
        else:
            p = head
            # 一直往后循环，直到找到尾结点（target_node）的前驱节点。
            while p.next != target_node:
                p = p.next
            p.next = None
            return head

Question 2

思路

删除链表中重复的节点。在一个排序的链表中，如何删除重复的节点？这道题和 LeetCode-82-删除排序链表中的重复元素-II 是一样的，出现的重复数字都要去除掉，利用双指针解决即可。

注意须将正常情况放在 if-elif-else 的最后，先判定是否重复再做常规情况的处理。is_pure 用于标记所有节点都是重复的这种特殊情况。

测试用例

功能测试（重复的节点位于链表的头部/中间/尾部；链表中没有重复的节点）。 特殊测试（指向链表头节点的为 nullptr 指针；链表中所有节点都是重复的）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:  return None
        if head and not head.next: return head
        is_pure = True
        dummy = ListNode(None)  # 声明哑结点
        dummy.next = head  # head肯定不会变
        p = head
        last = None
        pre_p = dummy
        while p and p.next:
            if p.val == p.next.val:  # 出现重复数字
                p.next = p.next.next
                last = p.val
			# 不满足p.val == p.next.val且p.val == last就说明当前p位于重复数字结束的节点。
            elif p.val == last:
                pre_p.next = p.next
                p = p.next
                is_pure = False
            else:  # 正常情况
                pre_p = p
                p = p.next
                is_pure = False
        
        if last == p.val:  # 防止结尾为重复数字的情况 [1, 2, 2]
            pre_p.next = p.next

        return None if is_pure else dummy.next  # 防止全是一个数字的情况 [1, 1, 1]