Python只删除该节点的访问权限,删除链表中的节点

Question

这是一个LeetCode问题,我知道它的解决方案,但想知道为什么我的代码不起作用.

编写一个函数来删除单链表中的节点(尾部除外),只允许访问该节点.

假设链表是1 - > 2 - > 3 - > 4,你给第三个节点值3,调用你的函数后链表应该变成1 - > 2 - > 4

乍一看,我的直觉是像数组一样删除:

将所有节点值移到前面,然后删除尾部,这是我的实现和测试用例:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5



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


deleteNode(node4)

但删除后,它有两个5个值节点,尾部仍保留,有人可以向我解释这里有什么问题吗？

deleteNode(node4)

node1.val
Out[162]: 1

node1.next.val
Out[163]: 2

node1.next.next.val
Out[164]: 3

node1.next.next.next.val
Out[165]: 5

node1.next.next.next.next.val
Out[166]: 5

真的很感激任何帮助.

Answer 1

你几乎就在那里,但正在做太多的工作,将所有 val值都移到一个节点上.您也无法清除最后一个next参考,这就是您看到5打印两次的原因.我将首先向您展示如何正确解决问题,然后解决尾部问题.

你可以通过不删除节点来解决这个难题,只需将其设置value为下一个值,然后next指向下一个节点之后的节点即可.这就是您需要做的所有事情,您无需触摸以下任何节点.您将有效地删除下一个节点,并使该节点保持下一个值:

      node
       |
       v
      ---------        ---------       
---> | val: va | ---> | val: vb | ---> ?
      ---------        ---------     

变

      node
       |
       v
      ---------        ---------       
---> | val: vb | -+   | val: vb |   -> ?
      ---------   |    ---------   |   
                  |                |
                   ----------------

所以实现很简单:

def deleteNode(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

不需要循环.

回到您的尝试,请注意您的函数中的最后一行无效.node是函数中的本地名称,并引用尾部ListNode实例,直到您将其设置为None.

你有这个:

      node
       |
       v
      -----------       
---> | val: tail | ---> None 
      ----------- 

而node = None做到这一点:

      node -> None
       X
       |
       v
      -----------       
---> | val: tail | ---> None 
      ----------- 

来自前一节点的传入引用仍然存在.

.next一旦完成循环,您必须跟踪"一个但最后一个"节点引用并清除该属性:

while node.next:
    node.val = node.next.val
    prev, node = node, node.next

# clear reference to tail
prev.next = None