删除链表结点-替身法 2020-09-18（未允禁转）

leetcode 237. 删除链表中的节点

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list

给定一个链表中的结点并且删除它，但不知道链表的head

思路1：
模拟数组remove掉一个元素的实现，把后一结点的val覆盖到前一结点，然后删除最后一个元素

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        slow = node
        fast = node.next
        while True:
            # 覆盖
            slow.val = fast.val

            if fast.next:
                fast = fast.next
                slow = slow.next
            else:
                slow.next = None
                break

思路2：
用数组的方式实现链表结点的删除是很苯的办法了，时间复杂度O(n)
链表不占用连续的存储空间，这给它的增加和删除带来了极大便利，只要稍微移动一下next指针就可以搞定。我们要充分感悟这一点

在上面的方法中，我们本质上是删除了链表的末尾结点对象，而不是node对象，末尾结点成为node的替身被真正删除。这给了我们启发，我们要删除一个结点node，也未必真的需要删除node，可以把node先变成某个合法结点N的克隆，让node以N的身份存在，然后删掉替死鬼结点N，也可以达到删除结点node的效果。
只要我变成你取代你，我就不会死了，那么你去死吧，还真有点阴暗呢

于是，我们用node取代其next结点，然后移动一下node.next就结束了，时间空间复杂度都是O(1)

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next