删除链表中具有给定键的节点

Question

我很难弄清楚我的代码出了什么问题。我想删除包含特定项的所有节点。在我的代码下面的测试代码中，它要求我删除"to"或"not to be"句子中的所有项目，然后返回标题，在这种情况下是"be"。有人能指出我的代码的问题吗?谢谢你。

package edu.csc130.assignment;
import java.util.LinkedList;
public class ListStackQueue {
/**
 * @param head the head of the input linked list
 * @param item the given value
 * @return the head of the linked list with nodes contains the given value removed
 * Assume for any node in the  linked list, node.item cannot be null
 */
  public static Node<String> removeNodes(Node<String> head, String item) {
    Node<String> curr = head;
    Node<String> prev = null;
    if (head == null) {
        System.out.println("list is empty");
    } else {
        while (curr != null) {
            if (curr.data != item) {
                prev = curr; 
                curr = curr.next; 
            } else if (curr == head && curr.data == item) {
                head = head.next; 
                curr = curr.next; 
            } else if (curr != head && curr.next != null && curr.data == item) {
                prev.next = curr.next; 
                curr = curr.next; 
            } else {
                curr.next = null; 
            }
        }   
    }
    return head;
  }
}

BuildList部分代码<——对不起，我没有把这部分代码放上去。感谢到目前为止帮助过我的人。

/**
 * @param items input array
 * @return the first node of the linked list build from the input array
 */
public static <E> Node<E>  buildList(E[] items) {
    Node<E> head = null;
    if (items!=null && items.length>0) {
        head = new Node<E> (items[0], null);
        Node<E> tail = head;
        for (int i=1; i<items.length; i++) {
            tail.next = new Node<E>(items[i], null);
            tail = tail.next;
        }
    }
    return head;
}
/**
 * @param head the first node of the linked list
 * @return the length of the linked list
 */
public static <E> int getLength(Node<E> head) {
    int length = 0;
    Node<E> node = head;
    while (node!=null) {
        length++;
        node = node.next;
    }
    return length;
}
public static <E> E get(Node<E> head, int index) {
    E item = null;
    Node<E> node = head;
    for (int i=0; i<index; i++) {
        if (node != null) {
            node = node.next;
        } else {
            break;
        }
    }
    if (node!=null) {
        item = node.item;
    }
    return item;
}
public static class Node<E> {
    public Object data;
    public String data();
    E item;
    Node<E> next;
    public Node(E item) {
        this.item = item;
        this.next = null;
    }
    public Node(E item, Node<E> next) {
        this.item = item;
        this.next = next;
    }
}

测试代码:

package edu.csc130.assignment;
import org.junit.Assert;
import org.junit.Test;
import edu.csc130.assignment.ListStackQueue.Node;
public class ListStackQueueTest {
  @Test
  public void testRemoveNodes1() {
    Node<String> head = ListStackQueue.buildList(null);
    ListStackQueue.removeNodes(head, "to");
    Assert.assertNull(head);
  }
  @Test
  public void testRemoveNodes2() {
    String[] sentence = {"to", "be", "or", "not", "to", "be"};
    Node<String> head = ListStackQueue.buildList(sentence);
    head = ListStackQueue.removeNodes(head, "to");
    Assert.assertEquals(4, ListStackQueue.getLength(head));
    Assert.assertEquals("be", ListStackQueue.get(head, 0));
    Assert.assertEquals("or", ListStackQueue.get(head, 1));
    Assert.assertEquals("not", ListStackQueue.get(head, 2));
    Assert.assertEquals("be", ListStackQueue.get(head, 3));
  } 
  @Test
  public void testRemoveNodes3() {
    String[] sentence = {"to", "be", "or", "not", "to", "be"};
    Node<String> head = ListStackQueue.buildList(sentence);
    head = ListStackQueue.removeNodes(head, "be");
    Assert.assertEquals(4, ListStackQueue.getLength(head));
    Assert.assertEquals("to", ListStackQueue.get(head, 0));
    Assert.assertEquals("or", ListStackQueue.get(head, 1));
    Assert.assertEquals("not", ListStackQueue.get(head, 2));
    Assert.assertEquals("to", ListStackQueue.get(head, 3));
  }     
  @Test
  public void testRemoveNodes4() {
        String[] sentence = {"to", "be", "or", "not", "to", "be"};
        Node<String> head = ListStackQueue.buildList(sentence);
        head = ListStackQueue.removeNodes(head, "or");
        Assert.assertEquals(5, ListStackQueue.getLength(head));
        Assert.assertEquals("to", ListStackQueue.get(head, 0));
        Assert.assertEquals("be", ListStackQueue.get(head, 1));
        Assert.assertEquals("not", ListStackQueue.get(head, 2));
        Assert.assertEquals("to", ListStackQueue.get(head, 3));
        Assert.assertEquals("be", ListStackQueue.get(head, 4));
      }
}

这是我在Eclipse中使用JUnit测试运行代码时得到的错误。这是testRemoveNodes2测试的错误。teststremovenodes1测试没有错误。

java.lang.AssertionError: expected:<4> but was:<6>

Answer 1

我看到你的程序不会工作的唯一方法是，如果使用==和!=的curr.data和item的比较不像预期的那样工作。这是完全可能的，因为不推荐使用这些操作符比较字符串，这不是一种常见的做法，除非你真的知道你在做什么(优化)，否则它们不会像你期望的那样。

例如，如果在ListStackQueue.buildList的实现中，您使用new String(...)创建节点的data字段的值。如果您以这种方式创建值，那么s1 == s2将永远不会为两个字符串为真，即使它们的值相同。

底线是，不要使用==和!=比较字符串，重写你的实现使用.equals代替，然后就可以了。当然，当你这样做的时候，在一个对象上调用.equals之前，你需要首先验证它不是空的，否则你会得到一个NullPointerException。

假设没有节点的data字段是null，这应该工作:

if (head == null) {
    System.out.println("list is empty");
} else {
    while (curr != null) {
        if (!curr.data.equals(item)) {
            prev = curr; 
            curr = curr.next; 
        } else if (curr == head) {
            head = head.next; 
            curr = curr.next; 
        } else if (curr != head && curr.next != null) {
            prev.next = curr.next; 
            curr = curr.next; 
        } else {
            curr.next = null; 
        }
    }   
}
return head;

我还去掉了一些多余的条件。

如果你想允许Node.data的null值，那么上面的!curr.data.equals(item)会更复杂一点，将其替换为:

        if (curr.data == null && item != null || curr.data != null && !curr.data.equals(item)) {