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

Question

Linked-List: Mirror

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

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

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

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

public void mirror();

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

начало 1 2 3

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

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

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

Answer 1

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 2

Поскольку Морис предоставил петлевое решение , я предоставлю рекурсивное решение.

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;
}

Answer 3

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

Answer 4

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

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