0

我必须以包的形式实现一个链表。通常，袋子没有移除，但在这种情况下，我需要一个。

当我运行我的测试客户端并调用 remove 时，我的链表中该项目的所有实例都被删除，除了第一个值。

所以基本上我的输出看起来像这样：

removed all 9s: 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 1 1 1 1 1 4 4 3 3 2 2 1 1 
removed all 3s: 4 4 4 4 4 2 2 2 2 2 1 1 1 1 1 4 4 2 2 1 1 
removed all 1s: 4 4 4 4 4 2 2 2 2 2 4 4 2 2
removed all 4s: 4 2 2 2 2 2 2 2 
removed all 2s: 4

这是我的代码：

public void remove (int item)
{
  // TODO
  Node previous = null; 
  Node current = first;

  if (first == null) // list is empty do nothing
  {
  }
  else if (first.item == item) // item occurs in first node 
  {
    //previous = first;
    first = first.next;
  } // skip around first node
  else
  {
    // find the node before item                                            
    for (Node p = first.next, q = first; p != null; q = p, p = q.next)
    {
      if (p.item == item)
      {
        q.next = p.next;
        //p.next = q.next;
        //return;            
      }
    }
  }

  while (current != null)
  {
    if(current.item == item)
    {
      current = current.next;            
      if (previous == null)
        previous = current;
      else
        previous.next = current;
    }
    else
    {
      previous = current;
      current = current.next;
    }
  } //end while
  //return;
}

这是测试客户端代码：

b1.remove(9);
print ("removed all 9s", b1); // does nothing
b1.remove(3);

print ("removed all 3s", b1);
b1.remove(1);

print ("removed all 1s", b1);
b1.remove(4);

print ("removed all 4s", b1);
b1.remove(2);

print ("removed all 2s", b1); // should be empty

有人可以帮我弄清楚为什么应该删除后 4 仍然存在吗？

4

1 回答 1

0

所以问题出在这条线上

if (previous == null){previous = current;}

前三个项目是 4。
在 remove(4) 上，遵循的步骤是
first = first.next//First 指向第二个项目 4 但 current 仍然指向第一个项目 4。
if(current.item == item) current = current.next//现在 current 也指向第二个 4。
previous = current// 由于 previous 为 null，所以if 语句为真，previous 也指向第二个 4。

在进一步的 while 循环中，previous 不为 null，您将 current 分配给 previous.next。所以你从来没有跳过第二个 4。

更新：假设您有一个节点head指向一个虚拟节点，后面跟着其他节点。

remove(item)
{
    previous = head;
    current = head.next;
    while(current!=null)
    {
        if(current.item == item)
        {
            previous.next = current.next;
            current = current.next;
        }
        else
        {
            previous = current;
            current = current.next;
        }
    }
}
于 2013-07-01T19:16:37.820 回答