Create a mirrored linked list in Java

Question

Linked-List: Mirror

Consider the following private class for a node of a singly-linked list of integers:

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

A wrapper-class, called, ListImpl, contains a pointer, called start to the first node of a linked list of Node.

Write an instance-method for ListImpl with the signature:

public void mirror();

That makes a reversed copy of the linked-list pointed to by start and appends that copy to the end of the list. So, for example the list:

start 1 2 3

after a call to mirror, becomes:

start 1 2 3 3 2 1

Note: in your answer you do not need to dene the rest of the class for ListImpl just the mirror method.

Answer 1

What is your question? This looks like an exercise problem. Are you looking for an optimized solution? One way would be to just iterate over the list and add elements to a stack and finally add them as nodes after the iteration.

Answer 2

You can make use of this approach:

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

Since Maurice provided a looping solution, I will provide a recursive 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;
}