如何在Ruby中为链表实现#pop函数

huangapple go评论65阅读模式
英文:

How to implement #pop for a Linked List in Ruby

问题

I'm struggling to find a solution for implementing #pop on a LinkedList structure in Ruby. I've currently got my implementation to the point of removing the last element (by setting the @next_node element to nil on the penultimate node) and returning the new last element, but I need my method to remember and return all of the previous nodes that I've looped through also, and I'm struggling to find a way to do this. Can anybody please help me:

LinkedList example structure;

"#<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>>>>>"

My current #pop implementation:

  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

Updated working method following @tom-lord's answer:

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
英文:

I'm struggling to find a solution for implementing #pop on a LinkedList structure in Ruby. I've currently got my implementation to the point of removing the last element (by setting the @next_node element to nil on the penultimate node) and returning the new last element, but I need my method to remember and return all of the previous nodes that I've looped through also, and I'm struggling to find a way to do this. Can anybody please help me:

LinkedList example structure;

"#<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>>>>>"

My current #pop implementation:

  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

Updated working method following @tom-lord's answer:

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

答案1

得分: 3

以下是您的代码更新,并添加了一些注释以回顾您所做的事情:

def pop
  # 处理列表为空的特殊情况 -- 没问题。
  return if head.nil?

  # 将 `current_node` 设置为**倒数第二个**节点。
  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

这里有两个问题:

  1. 您返回的是倒数第二个节点,而不是最后一个节点。
  2. 您的代码将无法处理包含恰好1个节点的链表。

我将专注于修复(1),并留下(2)作为您自己解决的扩展部分。

def pop
  # 处理列表为空的特殊情况 -- 没问题。
  return if head.nil?

  # 使用更具描述性的变量名可以更清楚地表明正在发生什么
  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

注意:由于您要求只返回翻译好的部分,我已删除了注释以外的内容。

英文:

Here is your code updated with some comments to recap what you've done:

def pop
  # Handles the edge case where the list is empty -- fine.
  return if head.nil?

  # Sets `current_node` to the **SECOND-LAST** node.
  current_node = head
  current_node = current_node.next_node until current_node.next_node.next_node.nil?

  # Deletes the SECOND-LAST node's pointer
  current_node.next_node = nil
  
  # Returns the SECOND-LAST node (???!!)
  return current_node
end

There are two things going wrong here:

  1. You are returning the second-last node, not the last node.
  2. Your code will fail for a linked list that contains exactly 1 node.

I'll focus on fixing (1), and leave (2) as an extension for you to figure out.

def pop
  # Handles the edge case where the list is empty -- fine.
  return if head.nil?

  # Using a more descriptive variable name makes it clearer what's happening
  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

huangapple
  • 本文由 发表于 2023年4月17日 18:25:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/76034151.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定