1.题目

2. 思路分析

1.我们要设置一个虚拟头节点，因为这个虚拟头节点对于增加节点操作和删除节点操作都很方便。
2.仔细读题，题目中说链表中的节点下标是从0开始的。也就是说第一个节点下标为0。
3.增加节点和删除节点的操作我们都要获取到它前一个的节点。
4.对于边界条件的判断，我们都假设index=0的情况来判断。比如添加节点的边界条件判断，我们拿addAtIndex(index=0)去做。
5.这道题测试用例有个bug,就是AddAtIndex这个方法，测试用例可能会传一个负数索引进来，这种情况下，我们将负索引节点插入到第一个节点。

3.构造节点

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}

4.MyLinkedList类实现

class MyLinkedList {
    int size;
    ListNode head; //虚拟头节点

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    public int get(int index) {
        if (index > this.size - 1 || index < 0)
            return -1;
        else {
            int count = 0;
            ListNode cur = head.next;
            while (count < index) {
                cur = cur.next;
                count++;
            }
            return cur.val;
        }
    }

    public void addAtHead(int val) {
        ListNode addNode = new ListNode(val);  //新建要插入的节点
        addNode.next = head.next;
        head.next = addNode;
        size++;

    }

    public void addAtTail(int val) {
        ListNode addNode = new ListNode(val);
        ListNode cur = head;
        //cur要到最后一个节点
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = addNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return; //什么也不用干
        }
        //如果索引小于0,则插入到头节点
        if (index < 0) {
            index = 0;
        }

        //找到要插入的位置(即cur指向  index对应节点的前一个节点)
        ListNode cur = head;
        int count = 0;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        //创建要插入的节点
        ListNode addNode = new ListNode(val);

        addNode.next = cur.next;
        cur.next = addNode;

        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) {
            return;
        }

        //找到要删除的节点的前一个节点,即cur指向要删除的节点的前一个节点
        ListNode cur = head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        cur.next = cur.next.next;
        size--;
    }
}