删除单链接Lis中的最后一个节点

Question

我能查一下吗 如何从单个链接列表中删除最后一个节点？在

这和我们移除第一个节点的方式相同吗？在

删除第一个节点

def deleteAtHead(self):
    temp = self.head
    self.head = self.head.next
    delete temp

删除最后一个节点

^{pr2}$

Answer 1

你必须从头部开始爬回tail。 尾部是第一个没有next的节点：next is None。 跟踪倒数第二个（prev），将其next设置为None。在

def deleteAtTail(self):   # remove_last would likely be a better name
    """ removes the last element of the singly linked list
    """
    temp = self.head
    while(temp.next is not None):
        prev  = temp
        temp = temp.next
    prev.next = None

将prev.next设置为None将删除尾节点（如果没有其他对它的引用，它将被垃圾回收）

Answer 2

因为这是一个单链链表，所以必须在tail之前遍历该列表以到达节点。我想你的职能应该是

def deleteAtTail(self):
     temp = self.head
     while(temp.next != None):
         if temp.next == tail: #finds the node just before tail
             break
         temp = temp.next
     temp.next = None
     self.tail = temp

我们设置self.tail = temp，因为temp等于列表末尾之前的节点。所以我们删除temp（通过删除它的最后一个引用），然后将tail设置为我们先前标识为列表中倒数第二个节点的节点，因为它实际上是列表的新结尾。在

编辑：

以解决一些对此答案的评论所关注的问题。在处理单链或双链表时，最好保持head、tail和{}指针。知道tail的位置对于在列表中插入计算上合理的内容是非常有价值的。在

这意味着您的插入方法可以从以下位置开始：

^{pr2}$

时间复杂度为O（n）：

def insert(value):
    self.tail.next = Node()
    self.tail.next.value = value
    self.tail = self.tail.next

它具有O（1）的更有利的时间复杂度。在

Answer 3

不能在O（n）=c复杂度的单链表中执行删除操作，因为您没有对前一个列表节点的引用。您必须遍历到列表的末尾，记住当前节点和上一个节点，然后将上一个节点从引用中修剪到下一个节点，下一个节点是您要删除的最后一个节点。对于单链表，这将始终具有O（n）=n的复杂性。在