Reverse a generalized version of bidirectional list (with 'aux, not just 'previous') in Java.

GeneralizedBiDiList.java

package marksto.lang;

import java.util.UUID;

public class GeneralizedBiDiList {

    static class Node {
        String listId;
        int value;
        Node next;
        Node aux;

        Node(String listId, int value) {
            this.listId = listId;
            this.value = value;
        }

        @Override
        public String toString() {
            return listId + "->" + value;
        }
    }

    private String id;
    private Node head;
    private int size;

    public GeneralizedBiDiList() {
        id = UUID.randomUUID().toString().substring(0, 2);
    }

    public Node getHead() {
        return head;
    }

    public void add(int value) {
        Node node = head;
        if (node == null) {
            head = new Node(id, value);
            size = 1;
            return;
        }

        while (node.next != null) {
            node = node.next;
        }
        node.next = new Node(id, value);
        size += 1;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        Node node = head;
        if (node == null) {
            return id + "=[]";
        }

        StringBuilder sb = new StringBuilder(id + "=[");
        appendNode(node, sb);
        while (node.next != null) {
            sb.append(", ");
            node = node.next;
            appendNode(node, sb);
        }
        return sb.append("]").toString();
    }

    private void appendNode(Node node, StringBuilder sb) {
        sb.append("{");
        sb.append(node.value);
        sb.append(":");
        if (node.aux != null) {
            sb.append(node.aux);
        } else {
            sb.append(node.listId);
        }
        sb.append("}");
    }

    public GeneralizedBiDiList reverse() {
        /*
         * IMPLEMENTATION NOTES:
         * - returns a new instance with isomorphic structure
         * - leaves original list unchanged (restores its state)
         */
        GeneralizedBiDiList reversed = new GeneralizedBiDiList();
        Node node = head;
        if (node == null) {
            return reversed;
        }

        // 1st iter - insert doubling nodes
        Node tmp = new Node(reversed.id, node.value);
        Node tmpNext;
        while (node != null) {
            tmpNext = node.next;

            node.next = tmp;
            tmp.next = tmpNext;

            if (tmpNext != null) {
                tmp = new Node(reversed.id, tmpNext.value);
            }
            node = tmpNext;
        }

        // 2nd iter - transplant auxiliaries
        node = head;
        while (node != null) {
            if (node.aux != null) {
                node.next.aux = node.aux.next;
            }
            node = node.next.next;
        }

        // 3rd iter - separate lists & reverse
        node = head;
        tmpNext = null;
        while (node != null) {
            tmp = node.next;

            node.next = tmp.next;
            tmp.next = tmpNext;
            tmpNext = tmp;

            node = node.next;
        }

        reversed.head = tmp;
        reversed.size = size;

        return reversed;
    }

    public static void main(String[] args) {
        // empty list
        GeneralizedBiDiList list1 = new GeneralizedBiDiList();
        GeneralizedBiDiList list1reversed = list1.reverse();
        System.out.println(list1 + " of size " + list1.getSize());
        System.out.println(list1reversed + " of size " + list1reversed.getSize());

        // single-node list
        GeneralizedBiDiList list2 = new GeneralizedBiDiList();
        list2.add(1);
        GeneralizedBiDiList list2reversed = list2.reverse();
        System.out.println(list2 + " of size " + list2.getSize());
        System.out.println(list2reversed + " of size " + list2reversed.getSize());

        // multi-node list
        GeneralizedBiDiList list3 = new GeneralizedBiDiList();
        list3.add(1);
        list3.add(2);
        list3.add(3);

        Node node1 = list3.getHead();
        Node node2 = node1.next;
        Node node3 = node2.next;
        node1.aux = node3; // reference to other node
        node2.aux = node2; // node self-reference

        GeneralizedBiDiList list3reversed = list3.reverse();
        System.out.println(list3 + " of size " + list3.getSize());
        System.out.println(list3reversed + " of size " + list3reversed.getSize());
    }

}