如何在Ruby中为Linked List实现#pop方法

问题分析 #

你当前的#pop方法能正确移除链表最后一个节点，但返回的是倒数第二个节点（新的尾节点），而我们需要返回的是被移除的原尾节点。问题出在你找到倒数第二个节点后，直接返回了它，没有提前保存原尾节点的引用。

你的链表结构示例：

#<LinkedList:0x000000010ced2508 @head=#<Node:0x000000010ced22b0 @value=13, @next_node=#<Node:0x000000010ced22d8 @value=2, @next_node=#<Node:0x000000010ced2300 @value=25, @next_node=#<Node:0x000000010ced2328 @value=20, @next_node=nil>>>>>

你的错误实现 #

def pop
  return if head.nil?
  current_node = head
  current_node = current_node.next_node until current_node.next_node.next_node.nil?
  current_node.next_node = nil
  return current_node
end

这段代码中，current_node最终指向倒数第二个节点，你把它的next_node置空后返回它，自然不是我们需要的被移除节点。

修正后的可行实现 #

def pop
  if head.nil?
    return head
  elsif head.next_node.nil?
    self.head = nil
    return head
  else
    second_last_node = head
    second_last_node = second_last_node.next_node until second_last_node.next_node.next_node.nil?

    last_node = second_last_node.next_node
    second_last_node.next_node = nil
    return last_node
  end
end

关键修正点 #

• 空链表处理：链表为空时直接返回nil，逻辑保持不变
• 单节点链表兼容：当链表仅有一个节点时，清空head后返回原头节点（即被移除的唯一节点）
• 多节点核心修复：
  1. 先定位到倒数第二个节点second_last_node
  2. 新增last_node变量保存原尾节点的引用（这是你之前遗漏的关键步骤）
  3. 将倒数第二个节点的next_node置空，完成移除操作
  4. 最后返回last_node，也就是被移除的原尾节点

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