如何反转链接列表的执行顺序？

我有一个名为LinkStrand的类，其功能与链接列表非常相似。它有toString()，size()，append()，next()和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; 
}

我一直在试图想出某种办法扭转节点顺序，但我画一个空白。有谁知道我会怎么做？

谢谢！

来源

2012-10-26 weskpga

反向实现是错误的，因为结果的最后一个元素！=原始的第一个元素，或者您必须在节点中实现接口Cloneable。或者你调用方法“reverseAndClone（）”。 –

如果您允许修改IDnaStrand和LinkStrand，请添加方法prepend(Node n)。然后，在遍历列表时，只需预先添加每个节点即可。

如果你不能修改你的班，Node S保存到一个数组中相反顺序（nodeArray[size-1]，nodeArray[size-2]，...），然后创建一个新的LinkStrand经历的数组中的顺序。或者，您可以按顺序加载阵列，然后在中创建LinkStrand反向命令。

例如：

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-26 10:42:29 durron597

创建一个新实例循环遍历原始数据并插入位置为0的新实例，然后返回它。

其他方式将排序它，但不能看到任何问题，将表明它目前排序。

来源

2012-10-26 10:40:23

你的回答假定他的LinkStrand类有一个prepend（），他没有说它有。 – durron597

我也不知道如何编写.prepend（），因为在我的构造函数中不需要指向下一个节点的指针。 – weskpga

@ durron597，好点 –

比方说，你的名单看起来是这样的：

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的下一个指针的list（空）的值的一个节点。现在是名单的结尾。

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-26 10:47:21 paddy

噢，是的，你可以在每个节点处反转字符串 – paddy

如何反转链接列表的执行顺序？

回答

相关问题