4

我必须为链表类编写一个非常简单的方法，但我遇到了一些问题。此方法称为squish()，采用此列表，并且在两个或多个连续项目相等的情况下（使用比较equals()），它会删除重复节点，以便仅保留一个连续副本。因此，该列表中没有两个连续项目在程序完成后是相等的。

执行后squish()，列表可能会比squish()开始时短。没有添加额外的项目来弥补那些被删除的项目。

例如，如果输入列表是[ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ]，则输出列表是[ 0 1 0 3 1 0 ]。

这是我的方法：

public void squish() {
 SListNode current = head;
 boolean end =false;

  while(end == false )
    {


      if(!current.item.equals(current.next.item))
          current=current.next;
      else
      {
          while(current.item.equals(current.next.item) && current.next !=null)
              current.next=current.next.next;
          current=current.next;

      }
    if (current==null)
        end=true;
    }


      }

这是执行代码的一个小主程序。

public class main {
public static void main(String args[])
{



    int[] test6 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3};
    SList list6 = new SList();
    for (int i = 0; i < test6.length; i++) {
      list6.insertEnd(new Integer(test6[i]));
    }
    System.out.println("squishing " + list6.toString() + ":");
    list6.squish();
    String result = list6.toString();
    System.out.println(result);


    int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
    SList list5 = new SList();
    for (int i = 0; i < test5.length; i++) {
      list5.insertEnd(new Integer(test5[i]));
    }

    System.out.println("squishing " + list5.toString() + ":");
    list5.squish();
    result = list5.toString();
    System.out.println(result);

}

}

调试代码我可以看到该方法工作正常..仅在列表末尾他会抛出一个空异常指针。你能帮助我吗？谢谢

4

3 回答 3

4

我会这样做：

public void squish() {
    SListNode current = head; //1

    if(current = null) return;  //1a

    while(current.next != null) { //2
       if(current.item.equals(currennt.next.item))
          current.next = current.next.next;  //3
       else 
          current = current.next;  //4
    }
}

这是教授喜欢为递归分配的那种东西，虽然大多数专业人士不使用递归，但我已经以这种方式设置了方法。

第 1 行是 init，您将遍历列表的指针分配到链表的开头。

第 1a 行如果列表中没有元素，则返回。

第 2 行是基本情况。如果列表中只有一个元素，则无事可做。

第 3 行是归纳，如果我们指向一个节点，我们检查隔壁的节点。如果它们具有相等的值，那么我们可以删除隔壁的节点。

第 4 行是第 3 行的 else，我们查看了隔壁的节点，发现它不相等。因此我们遍历列表。

手动遍历问题中提供的测试数据可能是一个有用的练习，然后在我的示例中添加一些 System.out.println 以查看您是否正确。我今天只需要使用一些棘手的代码来弄清楚发生了什么。

于 2013-07-15T20:36:34.770 回答
4

问题出在这一行：

while(current.item.equals(current.next.item) && current.next !=null)

在这里，条件的第一部分访问current.next.item，即使为空，因为条件 ( )current.next的第二部分在第一部分之后检查（并且仅当第一个计算结果为 时，见下文）。要修复它，只需反转条件：current.next !=nulltrue

while(current.next !=null && current.item.equals(current.next.item))

这样，表达式只有在为真（短路评估current.item.equals(current.next.item)）时才会被执行，也就是说，当这样做是安全的时候。current.next !=null

另外，我认为您可以放弃第一个if声明。看看@Pete 对如何简化方法的回答。

于 2013-07-15T20:40:48.097 回答
2

if(!current.item.equals(current.next.item))在最后一次迭代中执行该行时，current.next指向列表null中current的最后一项，实际上没有下一项。

编辑

现在在您的评论中，我看到您NullPointerException排在第一位

while(current.item.equals(current.next.item) && current.next !=null)

好吧，您应该将这两个条件相互替换：首先验证current.next不是null，然后才等于current和next：

while(current.next !=null && current.item.equals(current.next.item))

顺便说一句，if(!current.item.equals(current.next.item))当您的列表只有一个元素时，您仍然会在行中获得 NPE。例如，要解决这个问题，您可以检查 if head.next == null。如果是这样，请不要首先启动while循环。

于 2013-07-15T20:36:54.300 回答