将链表转换为二叉树

Question

我有一个链接列表，它有两个链接 - next和another。最初，所有another都保存为null。现在，我试图将其转换为一个二叉树，next持有liftChild和another持有rightChild。不过，我想在O（n）和恒定空间中做到这一点。我尝试了很多。以下是我的代码。我正在通过遍历生成树的级别顺序来验证结果。目前，我知道什么是错误，但不知道如何解决它。这里的错误是在while循环内，我正在更改node的链接，但这意味着我不能在末尾执行node = node.next，因为node的next已经指向列表中的某个位置。所以，我不知道如何遍历每个节点。任何提示，帮助表示赞赏。不是hw，不是面试问题或任何事情。试图学习数据结构。所以，这棵树和东西！

public class LlToBt { 

    public SpecialNode llToBt(SpecialNode node) { 
    SpecialNode temp = node; 
    SpecialNode returnNode = node; 

    if(node == null) 
     return null; 
    if(node.next == null) 
     return node; 

    node = returnNode; 
    while(node != null) { 
     SpecialNode currentNode = node; 

     temp = temp.next; 
     if(temp == null) { 
     //node.next = null; 
     //node.another = null; 
     return returnNode; 
     } 
     node.next = temp; 

     temp = temp.next; 
     if(temp == null) { 
     //node.next = null; 
     //node.another = null; 
     return returnNode; 
     } 
     node.another = temp; 

     node = currentNode.next; 

    } 

    return returnNode; 
    } 
} 

Answer 1

如果改变了，你会想你穿越它之前穿过的链接，那么你就需要关前把结果保存在一个不同的变量遍历的更改了链接。然后在更改之后，您可以使用临时副本进行遍历。