0

我有一个名为 LinkStrand 的类，它的功能与链接列表非常相似。它有, toString(), size(), append(), next()and value()，但不是previous()方法。我正在尝试编写反转节点顺序的代码，以及每个节点内的字符串。为了使自己在必须编写的其他一些方法中更轻松，我摆脱了构建节点时的下一个节点要求。下面是 Node 类的样子：

private class Node {
    public Node myNext;
    public String myData;

    Node(String value) {
        myData = value;
        //myNext = next;
    }   
}

我的 .reverse() 方法当前单独反转节点内的所有字符串，但不反转节点本身的顺序。复制如下：

public IDnaStrand reverse() {
    if (this == null)
        return this;
    Node prevStrand = null;
    Node thisStrand = myHead;
    String revString;
    LinkStrand val = new LinkStrand();
    while (thisStrand != null){
        Node hold = thisStrand.myNext;
        if (revSave.containsKey(thisStrand.myData)){
            revString = revSave.get(thisStrand.myData);
            val.append(revString);
            //System.out.println("Val is: " + val);
        }
        else{
            revString = reverseStr(thisStrand.myData);
            val.append(revString);
            //System.out.println("Val is: " + val);
            revSave.put(thisStrand.myData, revString);
        }
        thisStrand.myData = revString;
        thisStrand.myNext = prevStrand;
        prevStrand = thisStrand;
        thisStrand = hold;
    }
    return val;
}

我一直在尝试想出某种方法来反转节点顺序，但我正在画一个空白。有谁知道我该怎么做？

谢谢！

4

3 回答 3

2

如果允许修改IDnaStrandand LinkStrand，添加一个方法prepend(Node n)。然后，当您遍历列表时，只需预先添加每个节点。

如果您无法修改您的类，请将s 以相反的顺序 ( , , ...)保存Node到数组中，然后按顺序创建一个新的遍历数组。或者，您可以按顺序加载数组，然后以相反的顺序创建。nodeArray[size-1]nodeArray[size-2]LinkStrandLinkStrand

例子：

thisStrand = myHead;
int size = 0;
while(thisStrand != null){
    thisStrand = thisStrand.myNext;
    size++;
}
Node[] nodeArray = new Node[size];
thisStrand = myHead;
for(int i = size-1, i < 0; i--) {
    nodeArray[i] = thisStrand;
}

现在您有了数组，只需将其加载到新列表中！当然添加一个前置方法会更好，只要让类做

newElement.myNext = MyHead;
MyHead = newElement;
于 2012-10-26T10:42:29.727 回答
1

通过原始实例循环创建一个新实例，并在位置 0 处插入新实例，然后将其返回。

其他方法是对其进行排序，但在您的问题中看不到任何表明它当前已排序的内容。

于 2012-10-26T10:40:23.350 回答
0

假设您的列表如下所示：

A -> B -> C -> D -> E

我会缩短符号，因为我要写很多：

A B C D E

让我们取 3 个变量。我会展示他们的整个列表，这样你就可以看到发生了什么。第一项始终是存储在其中一个变量中的节点

list: null
curr: A B C D E
next: B C D E

将 A 的 next-pointer 设置为list(null) 的值。现在是列表的末尾。

list: null
curr: A
next: B C D E

现在，转到下一个：

list: A
curr: B C D E
next: C D E

你可以看到会发生什么。继续我们开始：将下一个指针设置curr为list：

list: B A
curr: B A
next: C D E

进步：

list: B A
curr: C D E
next: D E

再次：

list: C B A
curr: C B A
next: D E

等等...

伪代码相当简单：

list = null
curr = original_list

while next != null
    next = curr->next
    curr->next = list
    list = curr
    curr = next
end

所有这一切实际上是从列表的头部获取每个节点，并使其成为另一个列表的头部。这具有颠倒顺序的效果。我的回答可能有点啰嗦，但这就是你所做的一切。

于 2012-10-26T10:47:21.680 回答