设计自己的链表的实现。你可以选择使用单链表或者双链表。单链表中的节点应该具备两个属性：val 和 next。val 是当前节点的值，next 是下一个节点的指针。如果你想使用双链表，你需要多添加一个属性 prev 指向链表中前一个节点。假设链表中所有节点都是 0-indexed 的。

你的链表类需要实现以下函数：

• get(index) 获取链表中第 index 个节点的值。如果 index 无效，则返回 -1。
• addAtHead(val) 在链表的头部添加一个值为 val 的节点。在插入之后，新节点将会变成链表的第一个节点。
• addAtTail(val) 在链表的尾部添加一个值为 val 的节点。
• addAtIndex(index, val) 在链表中第 index 个节点之前添加一个值为 val 的节点。如果 index 等于链表的长度，新的节点将被添加到链表的尾部。如果 index 大于链表的长度，将不会添加节点。
• deleteAtIndex(index) 如果 index 有限，则删除链表中第 index 个节点。

举例：
输入：
[“MyLinkedList”,”addAtHead”,”addAtTail”,”addAtIndex”,”get”,”deleteAtIndex”,”get”]
[[],[1],[3],[1,2],[1],[1],[1]]
输出：
[null,null,null,null,2,null,3]

解释：

MyLinkedList linkedList = new MyLinkedList(); // 初始化空链表
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2);  // 链表变成 1->2->3
linkedList.get(1);            // 返回 2
linkedList.deleteAtIndex(1);  // 现在链表是 1->3
linkedList.get(1);            // 返回 3

限制：
0 <= index,val <= 1000
不要使用内置的链表类。
各函数最多会调用 2000 次。

/*
 * 707. Design Linked List
 * https://leetcode.com/problems/design-linked-list/
 * https://www.whosneo.com/707-design-linked-list/
 */

class MyLinkedList {

    ListNode dummyHead;

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

    private void print() {
        for (ListNode node = dummyHead.next; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    public MyLinkedList() {
        dummyHead = new ListNode(0);
    }

    public int get(int index) {
        ListNode node = dummyHead.next;
        for (int i = 0; i < index && node != null; i++) {
            node = node.next;
        }
        return node == null ? -1 : node.val;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = dummyHead.next;
        dummyHead.next = node;
    }

    public void addAtTail(int val) {
        ListNode node = dummyHead.next;
        while (node != null && node.next != null) {
            node = node.next;
        }
        if (node == null) {
            dummyHead.next = new ListNode(val);
        } else {
            node.next = new ListNode(val);
        }
    }

    public void addAtIndex(int index, int val) {
        ListNode node = dummyHead.next, prev = dummyHead;
        for (int i = 0; i < index && node != null; i++) {
            prev = node;
            node = node.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = node;
        prev.next = newNode;
    }

    public void deleteAtIndex(int index) {
        ListNode node = dummyHead.next, prev = dummyHead;
        for (int i = 0; i < index && node != null; i++) {
            prev = node;
            node = node.next;
        }
        if (node != null)
            prev.next = node.next;
        else
            prev.next = null;
    }
}