java - 如何通过交替数据结构来组合节点？ - java

Question

我得到了两个节点数据结构，我应该将它们组合成一个具有交替数据结构的节点。数据结构的长度可能相同，也可能不同。

我已经尝试过这个问题，并且检查了我的代码，但它仍然不正确。我已经编写了在这一特定方法中使用的其他方法，因此我也将发布这些方法的代码。我通过查看针对这个特定问题的数据组织如何工作的示例，想出了我的方法。

获取Node列表的头部:

public static <E> Node<E> getHead(Node<E> current) {
    Node<E> head = null;
    while (current != null) {
        head = current;
        current = current.previous;
    }
    return head;
}

获取数据结构中的节点数量:

public static <E> int countNodes(Node<E> current) {
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

请注意，我已经测试了这两种方法(getHead 和 countNodes)，并且它们已被证明是正确的。我已将它们发布以查看它们是否缺少某些内容。

Node 类本身是由我的导师编写的，并且已经过测试，编写正确

public static class Node<E> {
    public Node<E> next;
    public Node<E> previous;
    public E data;

    public Node(E d) {
        data = d;
    }

    public String toString() {
        if (next == null)
            return "";
        return data + ", " + next.toString();
    }

    public boolean equals(Object o) {
        Node<E> node = (Node<E>) o;
        if (node == null)
            return false;
        Node<E> current = this;
        while (current != null && node != null) {
            if (!current.data.equals(node.data)) {
                return false;
            }
            current = current.next;
            node = node.next;
        }
        return current == null && node == null;
    }
}

最后，我遇到问题的方法:(已编辑更新)

public static <E> Node<E> combineNodes(Node<E> current, Node<E> current2) {
    Node<E> newNode = null;
    int currentSize = countNodes(current);
    int current2Size = countNodes(current2);
    int size = Math.max(currentSize, current2Size);

    for (int i = 0; i < size; i++) {
        if (i <= currentSize - 1) {
            Node<E> node = new Node<E>(current.data);
            newNode.next = node;
            node.previous = newNode;
            newNode = newNode.next;
            current = current.next;
        }
        if (i <= current2Size - 1) {
            Node<E> node = new Node<E>(current2.data);
            newNode.next = node;
            node.previous = newNode;
            newNode = newNode.next;
            current2 = current2.next;
        }
    }

    return getHead(newNode);
}

我再次查看了代码，我觉得它应该可以工作。我有什么遗漏或做错的事情吗？

编辑

我应该包含给我的测试用例。我的讲师正在使用 JUnit 测试用例库来完成作业。这是我必须通过的测试用例:

@Test
public void combineNodesTest1() {
    LinkedData.Node<String> node = makeStructure(10); // Makes a data structure of Nodes from "Fred 0" to "Fred 9"
    LinkedData.Node<String> node2 = makeStructure(10);
    LinkedData.Node<String> ret = new LinkedData.Node<String>("Fred 0");
    ret.next = new LinkedData.Node<String>("Fred 0");
    LinkedData.Node<String> r = ret.next;
        for(int i = 1; i<10;i++) {
        r.next = new LinkedData.Node<String>("Fred "+i);
        r = r.next;
        r.next = new LinkedData.Node<String>("Fred "+i);
        r = r.next;
    }
    LinkedData.Node<String> answer = LinkedData.combineNodes(node, node2); // Method that I wrote
    assertEquals(ret, answer);
}

makeStructure()方法编写正确。

编辑2

我已经更新了代码以实际将节点链接在一起，但它仍然是错误的。我想知道我现在做错了什么。

谢谢，管家

Answer 1

从我的角度来看，您不会更改 combineNodes 方法中的任何指针(下一个、上一个)。您只需遍历该结构。第一个 if 中缺少的是

newNode = current;
newNode.next = current2;
current = current.next;

然后在第二个if中添加以下内容

newNode = current2;
newNode.next = current;
current2 = current2.next;