Преобразование связанного списка в двоичное дерево

Question

У меня есть связанный список, который имеет две ссылки: next и another. Первоначально все another провести null. Теперь я пытаюсь преобразовать это в двоичное дерево с next, удерживая liftChild и another, удерживая rightChild. Однако я хочу сделать это в O (n) и в постоянном пространстве. Я много пробовал. Ниже мой код. Я проверяю результат по порядку уровня, пересекающему полученное дерево. В настоящее время я знаю, в чем ошибка, но не знаю, как ее решить. Ошибка здесь в том, что внутри цикла while я правильно меняю ссылки node, но это означает, что я не могу сделать node = node.next в конце, потому что 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

Если вы меняете ссылку, которую вы хотите, чтобы пройти, прежде чем пройти через него, то вам нужно хранить в другом переменной, результатом обхода перед тем изменить ссылку. Затем после изменения вы можете перемещаться, используя свою временную копию.