Python链表remove_from_tail()方法实现需求及思路问询

没问题，这是满足你需求的最简LinkedList实现，包含__init__()、print_all()、add()和remove_from_tail()方法，其中remove_from_tail()严格通过curr和prev指针遍历定位尾节点：

首先我们需要一个基础的Node类来表示链表的节点：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

接下来是核心的LinkedList类：

class LinkedList:
    def __init__(self):
        # 初始化空链表，头节点为None
        self.head = None

    def print_all(self):
        # 遍历并打印所有节点的值
        curr = self.head
        while curr:
            print(curr.value, end=" -> ")
            curr = curr.next
        print("None")  # 标记链表结束

    def add(self, value):
        # 最简实现：将新节点添加到链表头部（时间复杂度O(1)）
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def remove_from_tail(self):
        # 处理空链表的情况
        if not self.head:
            print("链表为空，无法移除尾节点")
            return None
        
        # 处理只有一个节点的情况
        if not self.head.next:
            removed_value = self.head.value
            self.head = None
            return removed_value
        
        # 多个节点的情况：用curr和prev遍历找到尾节点
        prev = None
        curr = self.head
        while curr.next:
            prev = curr
            curr = curr.next
        
        # 移除尾节点，更新前一个节点的next指针
        removed_value = curr.value
        prev.next = None
        return removed_value

简单测试示例 #

你可以用下面的代码验证功能：

# 创建链表实例
ll = LinkedList()

# 添加元素
ll.add(10)
ll.add(20)
ll.add(30)

# 打印所有元素
print("初始链表：")
ll.print_all()  # 输出：30 -> 20 -> 10 -> None

# 移除尾节点
removed = ll.remove_from_tail()
print(f"移除的尾节点值：{removed}")  # 输出：10

# 再次打印
print("移除后的链表：")
ll.print_all()  # 输出：30 -> 20 -> None

关键说明 #

• add()方法这里默认添加到头部，因为这样实现最简单且效率最高（O(1)），如果需要添加到尾部可以调整，但会增加遍历的开销（O(n)）。
• remove_from_tail()严格按照你的要求，用curr指针遍历找尾节点，prev指针记录前一个节点，确保能正确更新链表的尾端。
• 所有方法都做了边界情况处理，比如空链表、单节点链表的场景。

内容的提问来源于stack exchange，提问作者Joker