Создать зеркальную связанный список в Java

Question

Linked-List: Зеркало

Рассмотрим следующий частный класс для узла однократно связанного списка целых чисел:

private class Node{ 
public int value; 
public Node next; 
} 

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

Напишите экземпляр-метод ListImpl с подписью:

public void mirror(); 

Это делает инверсное копию связанного списка, на который указывает начало и добавляет, что копируют до конца списка. Так, например, список:

начало 1 2 3

после вызова зеркало, становится:

начало 1 2 3 3 2 1

Примечание: в своем ответе вы не нужно добавить остальную часть класса для ListImpl только метод зеркала.

Answer 1

Что вы хотите сказать? Это похоже на проблему упражнений. Вы ищете оптимизированное решение? Один из способов - просто перебрать список и добавить элементы в стек и, наконец, добавить их как узлы после итерации.

Answer 2

Вы можете использовать этот подход:

Algorithm findLinkedListMirror 
    If list does not exist 
    return 

    Let start and end be pointers to type Node 
    Position start to the first node of the list 
    Position end to last node of the list 

    While(start != end.next) 
    Add a new node next to end with value start.data 
    start = start.next 
    End While 

End 

Answer 3

public void mirror() { 
    if (start != null) { 
     Node prev = null; 
     Node p = start; 
     Node q = null; 
     while (p != null) { 
      Node n = new Node(); 
      n.value = p.value; 
      n.next = q; 
      q = n; 
      prev = p; 
      p = p.next; 
     } 
     prev.next = q; 
    } 
} 

Answer 4

Поскольку Морис предоставил looping solution, обеспечит рекурсивное решение.

void mirror() 
{ 
    if (start == null) return; 
    mirrorSublist(start); 
} 

// returns the last node of the mirrored sublist 
Node mirrorSublist(Node firstOfSublist) 
{ 
    Node lastOfSublist = new Node(); 
    lastOfSublist.value = firstOfSublist.value; 
    lastOfSublist.next = null; 
    if (firstOfSublist.next == null) 
    { 
     firstOfSublist.next = lastOfSublist; 
    } 
    else 
    { 
     Node secondToLastOfSublist = mirrorSublist(firstOfSublist.next); 
     secondToLastOfSublist.next = lastOfSublist; 
    } 
    return lastOfSublist; 
}