707. 设计链表

一 题目：

二 思路：

• 因为题目又加又减的，我们用双链表比较方便
• 然后题目要快速找第一个和最后一个，因此我们需要俩节点快速找到第一个最后一个，但是链表可能会空，因此我们用俩虚拟节点比较好
• 题目大量存在根据长度判断操作有效无效，因此我们留一个字段记录长度。

三 代码：

public class MyLinkedList {
    //第一个节点的前虚拟节点
    DListNode pp;
    //最后一个节后的前虚拟节点
    DListNode tt;
    int len;


    public MyLinkedList() {
        this.pp = new DListNode();
        this.tt = new DListNode();
        this.len=0;
    }

    public int get(int index) {
        if (index>len-1){
            return -1;
        }

        //否则
        DListNode search=pp;
        for (int i = 0; i <=index ; i++) {
            search=search.next;
        }
        return search.val;
    }

    public void addAtHead(int val) {
        DListNode newHead = new DListNode();
        newHead.setVal(val);
        //如果是空链表
        if (pp.next==null&&tt.pre==null){
            pp.next=newHead;
            newHead.pre=pp;
            newHead.next=tt;
            tt.pre=newHead;
        }else {
            DListNode oldHead = pp.next;
            newHead.pre=pp;
            newHead.next=oldHead;
            pp.next=newHead;
            oldHead.pre=newHead;
        }
        len++;
    }

    public void addAtTail(int val) {
        DListNode newTail = new DListNode();
        newTail.setVal(val);
        //如果是空链表
        if (pp.next==null&&tt.pre==null){
            pp.next=newTail;
            newTail.pre=pp;
            newTail.next=tt;
            tt.pre=newTail;
        }else {
            DListNode oldTail = tt.pre;
            newTail.pre=oldTail;
            newTail.next=tt;
            tt.pre=newTail;
            oldTail.next=newTail;
        }
        len++;
    }

    public void addAtIndex(int index, int val) {
        DListNode newNode = new DListNode();
        newNode.setVal(val);

        if (index==0){
            addAtHead(val);
        }else if (index==len){
            addAtTail(val);
        }else if (index>len){
            return;
        }else {
            DListNode rep=pp;
            for (int i = 0; i <=index ; i++) {
                rep=rep.next;
            }
            DListNode pre = rep.pre;
            newNode.pre=pre;
            newNode.next=rep;
            pre.next=newNode;
            rep.pre=newNode;
            len++;
        }
        
    }

    public void deleteAtIndex(int index) {
        if (index>len-1){
            return;
        }
        //如果组内就一个元素，直接恢复出厂设置
        if (this.len==1){
            this.pp.next = null;
            this.tt.pre = null;
            this.len=0;
            return;
        }

        //否则
        DListNode del=pp;
        for (int i = 0; i <=index ; i++) {
            del=del.next;
        }
        DListNode pre = del.pre;
        DListNode next = del.next;
        pre.next=next;
        next.pre=pre;
        len--;
    }
}

class DListNode {
    int val;
    DListNode pre;
    DListNode next;

    public DListNode() {
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public DListNode getPre() {
        return pre;
    }

    public void setPre(DListNode pre) {
        this.pre = pre;
    }

    public DListNode getNext() {
        return next;
    }

    public void setNext(DListNode next) {
        this.next = next;
    }
}