灵神基础算法精讲-08-学习笔记

237. 删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
我们将构建链表，并将节点传递给你的函数。
输出将是调用你函数后的整个链表。

思路

题目只给要删除的节点，不知道它的上一个节点是谁，由于题目保证 node 不是链表中的最后一个节点，那么可以把下一个节点的值 copy 过来，然后把下一个节点删除，根据题目要求，给定节点值不存在于链表中就达到了删除节点的效果。

实现

def deleteNode(node):
    node.val = node.next.val
    node.next = node.next.next

对于删除节点来说，什么需要创建一个 dummy node 呢，如果需要删除一个头节点的话，创建一个 dummy node 比较合适。

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

如果 N 等于链表长度，头节点是会被删除的，那么就需要创建 dummy node。要想删除倒数第 N 个结点，需要找到倒数第 N + 1 个结点。初始化右指针指向 dummy node，先让右指针走 n 步，然后初始化左指针指向 dummy node，左右指针一起向右走，那么左右指针的距离始终为 N，当右指针走到最后一个结点，也就是倒数第一个结点，那么左指针恰好就走到了倒数第 n + 1 个结点，这样就可以做删除操作了。

做法

def removeNthFromEnd(head, n):
    dummy = ListNode(next = head)
    right = dummy
    for _ in range(n):
        right = right.next

    left = dummy
    while right.next:
        left = left.next
        right = right.next

    left.next = left.next.next
    return dummy.next

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

思路

这题不需要 dummy node，因为可以把头节点保留下来，初始化 cur 指向头结点，分类讨论一下，如果下一个结点存在，并且它的值和 cur 指向的节点值是相同的，那就删除下一个结点，否则就移到下一个结点，如此循环，直到 cur 后面没有结点为止。

做法

def deleteDuplicates(head):
    if head is None:
        return head

    cur = head
    while cur.next:
        if cur.next.val == cur.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    
    return head

82. 删除排序链表中的重复元素Ⅱ

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

思路

这题需要 dummy node，如果开头就有几个重复结点，那头节点是会被删除的。初始化 cur 指向 dummy node，每次循环的时候，看下一个结点和下下一个结点的值是不是一样的，如果一样，就再套一个循环，不断删除结点，直到没有结点，或者遇到的节点值不一样，就退出循环。如果后面这两个值不一样，那 cur 就移到下一个结点，直到后面不足两个结点为止。

def deleteDuplicates(head):
    dummy = ListNode(next = head)
    cur = dummy

    while cur.next and cur.next.next:
        val = cur.next.val
        if cur.next.next.val == val:
            while cur.next and cur.next.val == val:
                cur.next = cur.next.next
        else:
                cur = cur.next

    return dummy.next