package leetcode;

/**
 * https://leetcode.com/problems/design-linked-list/
 */
public class Problem707 {
    private static class MyLinkedList {
        private final static class Node {
            private final int value;
            private Node next;

            public Node(int value) {
                this.value = value;
            }

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

        private Node head;
        private Node tail;

        /** Initialize your data structure here. */
        public MyLinkedList() {
        }

        /**
         * Get the value of the index-th node in the linked list. If the index is invalid,
         * return -1.
         */
        public int get(int index) {
            int idx = 0;
            for (Node n = head; n != null; n = n.next) {
                if (idx++ == index) {
                    return n.value;
                }
            }
            return -1;
        }

        /**
         * Add a node of value val before the first element of the linked list.
         * After the insertion, the new node will be the first node of the linked list.
         */
        public void addAtHead(int val) {
            if (head == null) {
                head = new Node(val);
                tail = head;
            } else {
                head.next = new Node(val);
                head = head.next;
            }
        }

        /** Append a node of value val to the last element of the linked list. */
        public void addAtTail(int val) {
            if (tail == null) {
                tail = new Node(val);
                head = tail;
            } else {
                tail.next = new Node(val);
                tail = tail.next;
            }
        }

        /**
         * Add a node of value val before the index-th node in the linked list.
         * If index equals to the length of linked list, the node will be appended
         * to the end of linked list. If index is greater than the length, the node
         * will not be inserted.
         */
        public void addAtIndex(int index, int val) {
            if (index == 0) {
                addAtHead(val);
                return;
            }
            int idx = 0;
            for (Node n = head; n != null; n = n.next) {
                if (idx == index - 1) {
                    Node tmp = n.next;
                    n.next = new Node(val);
                    n.next.next = tmp;
                }
                idx++;
            }
        }

        /** Delete the index-th node in the linked list, if the index is valid. */
        public void deleteAtIndex(int index) {
            int idx = 0;
            for (Node n = head; n != null; n = n .next) {
                if (idx == index + 1) {
                    Node tmp = n.next;
                    // TODO
                }
            }
        }
    }

    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        System.out.println(linkedList.get(0)); // 1
        System.out.println(linkedList.get(1)); // 3
        linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
        System.out.println(linkedList.get(1)); // returns 2
    }
}

@@ -340,119 +340,8 @@
    %7D
-%0A%0A            @Override%0A            public String toString() %7B%0A                return %22%22 + value;%0A            %7D
 %0A   
@@ -401,16 +401,42 @@
 de tail;
+%0A        private int size;
 %0A%0A      
@@ -1288,25 +1288,53 @@
         
-head.next
+Node tmp = head;%0A                head
  = new N
@@ -1367,20 +1367,19 @@
 head
- = head.next
+.next = tmp
 ;%0A  
@@ -1382,32 +1382,52 @@
 ;%0A            %7D%0A
+            size++;%0A
         %7D%0A%0A     
@@ -1747,32 +1747,52 @@
 ;%0A            %7D%0A
+            size++;%0A
         %7D%0A%0A     
@@ -2235,32 +2235,135 @@
 ;%0A            %7D%0A
+            if (size == index) %7B%0A                addAtTail(val);%0A                return;%0A            %7D%0A
             int 
@@ -2582,32 +2582,87 @@
 ext.next = tmp;%0A
+                    size++;%0A                    break;%0A
                 
@@ -2850,35 +2850,56 @@
            i
-nt id
+f (size == 0 %7C%7C inde
 x 
+%3E
 = 
-0;
+size) %7B
 %0A           
@@ -2903,58 +2903,34 @@
     
-for (Node n = head; n != null; n = n .next) %7B%0A
+    return;%0A        
     
+%7D%0A
     
@@ -2945,24 +2945,18 @@
 if (
-idx == 
 index 
-+ 1
+== 0
 ) %7B%0A
@@ -2971,32 +2971,27 @@
         
-  
-  Node tmp = n
+head = head
 .next;%0A 
@@ -3009,465 +3009,499 @@
     
-    // TODO%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        MyLinkedList linkedList = new MyLinkedList();%0A        linkedList.addAtHead(1);%0A        linkedList.addAtTail(3);%0A        System.out.println(linkedList.get(0)); // 1%0A        System.out.println(linkedList.get(1)); // 3%0A        linkedList.addAtIndex(1, 2); // linked list becomes 1-%3E2-%3E3%0A        System.out.println(linkedList.get(1)); // returns 2
+size--;%0A                if (size == 0) %7B%0A                    tail = null;%0A                %7D%0A                return;%0A            %7D%0A            int idx = 0;%0A            for (Node n = head; n != null; n = n .next) %7B%0A                if (idx++ == index - 1) %7B%0A                    if (n.next == tail) %7B%0A                        tail = n;%0A                    %7D%0A                    n.next = n.next.next;%0A                    size--;%0A                    break;%0A                %7D%0A            %7D%0A        %7D
 %0A   

Solve problem 707