Skip to content

237 delete node in a linked list

237. Delete Node in a Linked List

题目: https://leetcode.com/problems/delete-node-in-a-linked-list/

难度: Easy

这道题,第一感觉,像删链表一样来删,把所有的node val前移一个,但是有个问题,为什么tail那个node还是存在?哼(ˉ(∞)ˉ)唧..

已经被解答:

http://stackoverflow.com/questions/38879291/python-delete-a-node-in-linked-list-given-just-access-to-that-node

另外一个O(1)的办法更好,把后一个node的val移到待删这个节点,并且把node.next = node.next.next

题目说了不会删最后一个点,所以node.next.next一定存在,所以直接让node的val等于它next的val,然后让node的next指向它的next的next,举个例子: 1->2->3->4->5->None,要删除第四个节点,就让4变成5,然后让第四个节点指向第五个节点的next, 这样原来的第四个节点就不存在了,虽然原来的第五个节点仍然存在且指向None,变成了1->2->3->5->None-<5

O(1)时间
class Solution(object):
    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
O(n)时间
class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        while node.next:
            node.val = node.next.val
            prev, node = node, node.next
        # clear reference to tail
        prev.next = None


回到顶部