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

Question

我可以检查一下吗我们如何从单个链表中删除最后一个节点？

和我们移除第一个节点的方式一样吗？

删除第一个节点

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

删除最后一个节点

def deleteAtTail(self):
    prev = None
    temp = self.tail
    self.tail= self.tail.prev 
    delete temp

Answer 1

因为这是一个单向链表，所以您必须遍历链表才能到达尾部之前的节点。我认为您的功能只需要

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 和 current 指针。知道 tail 的位置对于在列表中插入计算上合理的东西非常有价值。

这意味着您的插入方法可以是这样的：

def insert(value):
    temp = self.head
    while(temp.next != None):
        temp = temp.next
    temp.next = Node()
    temp.next.value = value

时间复杂度为 O(n)：

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

它具有更有利的 O(1) 时间复杂度。

Answer 2

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

Answer 3

你必须爬回到 tail 从头开始。尾部是没有下一个的第一个节点：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会删除尾节点（如果没有其他引用，它将被垃圾回收）

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

Removing the lastNode in a singly Linked List

python

singly-linked-list