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
回到顶部