/**
 * An SLList is a list of integers, which encapsulates the
 * naked linked list structure.
 */
public class SLList {

    /**
     * IntListNode is a nested class that represents a single node in the
     * SLList, storing an item and a reference to the next IntListNode.
     */
    private static class IntListNode {
        /*
         * The access modifiers inside a private nested class are irrelevant:
         * both the inner class and the outer class can access these instance
         * variables and methods.
         */
        public int item;
        public IntListNode next;

        public IntListNode(int item, IntListNode next) {
            this.item = item;
            this.next = next;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            IntListNode that = (IntListNode) o;
            return item == that.item;
        }

        @Override
        public String toString() {
            return item + "";
        }

    }

    /* The first item (if it exists) is at sentinel.next. */
    private IntListNode sentinel;
    private int size;

    /** Creates an empty SLList. */
    public SLList() {
        sentinel = new IntListNode(42, null);
        sentinel.next = sentinel;
        size = 0;
    }

    public SLList(int x) {
        sentinel = new IntListNode(42, null);
        sentinel.next = new IntListNode(x, null);
        sentinel.next.next = sentinel;
        size = 1;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        SLList other = (SLList) o;
        SLList slList = (SLList) o;
        if (size != slList.size) return false;

        IntListNode l1 = sentinel.next;
        IntListNode l2 = slList.sentinel.next;

        while (l1 != sentinel && l2 != slList.sentinel) {
            if (!l1.equals(l2)) return false;
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

    @Override
    public String toString() {
        IntListNode l = sentinel.next;
        StringBuilder result = new StringBuilder();

        while (l != sentinel) {
            result.append(l).append(" ");
            l = l.next;
        }

        return result.toString().trim();
    }

    /** Returns an SLList consisting of the given values. */
    public static SLList of(int... values) {
        SLList list = new SLList();
        for (int i = values.length - 1; i >= 0; i -= 1) {
            list.addFirst(values[i]);
        }
        return list;
    }

    /** Returns the size of the list. */
    public int size() {
        return size;
    }

    /** Adds x to the front of the list. */
    public void addFirst(int x) {
        sentinel.next = new IntListNode(x, sentinel.next);
        size += 1;
    }

    /** Return the value at the given index. */
    public int get(int index) {
        IntListNode p = sentinel.next;
        while (index > 0) {
            p = p.next;
            index -= 1;
        }
        return p.item;
    }
    
    /** Adds x to the list at the specified index. */
    public void add(int index, int x) {
        // sentinel.next doesn't update if we use normal logic
        if (index == 0) {
            addFirst(x);
            return;
        }
        
        index = Math.min(index, size);
        
        IntListNode prev = sentinel.next;
        
        while (index - 1 > 0) {
            prev = prev.next;
            index -= 1;
        }
        
        prev.next = new IntListNode(x, prev.next);
        
        size++;
    }
    
    /** Destructively reverses this list. */
    public void reverse() {
        // There's no point in reversing an empty or 1-element list
        if (size > 1) {
            IntListNode head = sentinel.next;
            IntListNode tail = head.next;
            sentinel.next = reverseHelper(head, tail);
        }
    }
    
    public IntListNode reverseHelper(IntListNode head, IntListNode tail) {
        // Base case: head is the only item in the list to "reverse"
        if (tail.equals(sentinel)) {
            return head;
        }
        
        // General case: append head to end of reversed list
        IntListNode tailHead = tail;
        IntListNode tailTail = tail.next;
        tail = reverseHelper(tailHead, tailTail);
        IntListNode reversedStartPointer = tail;
        
        while (!tail.equals(sentinel)) {
            tail = tail.next;
        }
        
        tail.next = head;
        
        return reversedStartPointer;
    }
}