题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例

第一次提交的代码

class MyLinkedList {

    private int val;
    private MyLinkedList next;

    //指针指向最后一个节点
    private MyLinkedList last;
    //指针指向第一个节点
    private MyLinkedList first;
    //当前链表的长度
    private int length;

    public MyLinkedList() {
        next=null;
        //代表当前节点没有值
        val=-2;
        first=this;
        last=this;
        length=0;
    }

    public MyLinkedList(int val,MyLinkedList next){
        this.val=val;
        this.next=next;
    }

    public int get(int index) {
        //处理不合理的index值
        if(index<0||index>=length)return -1;

        MyLinkedList p=new MyLinkedList();
        p=this.first;
        while(index>0){
            p=p.next;
            index--;
        }

        return p.val;
    }

    public void addAtHead(int val) {
        if(this.val==-2){
            this.val=val;
            this.first=this;
            this.last=this;
        }
        MyLinkedList newNode=new MyLinkedList();
        newNode.next=this.first;
        newNode.val=val;
        this.first=newNode;
        this.length++;
    }

    public void addAtTail(int val) {
        int num=this.length-1;
        MyLinkedList p=new MyLinkedList();
        p=this.first;
        while(num>0){
            p=p.next;
            num--;
        }
        MyLinkedList newNode=new MyLinkedList();
        newNode.val=val;
        newNode.next=null;
        p.next=newNode;
        this.last=newNode;
        this.length++;
    }

    public void addAtIndex(int index, int val) {
        //处理不合理的index值
        if(index<0||index>=length)return;
        if(index==0){
            this.addAtHead(val);
            return;
        }
        MyLinkedList p=new MyLinkedList();
        p=this.first;
        int num=index-1;
        while(num>0){
            p=p.next;
            num--;
        }
        MyLinkedList newNode=new MyLinkedList();
        newNode.val=val;
        newNode.next=p.next;
        p.next=newNode;
        this.length++;
    }

    public void deleteAtIndex(int index) {

        MyLinkedList current=this.first;


        MyLinkedList pre =null;
        int num=index;
        while(num>0){
            pre=current;
            current=current.next;
            num--;
        }

        pre.next=current.next;

        this.length--;
    }
}

结果就是通过不了:(，我自己在设计的时候，总觉得每个对象里面都带有length,first,next指针这些东西好奇怪啊，膈应的慌，最后一些方法修改一下应该可以通过。唉，菜了菜了。

学习到的东西

我怎么就没想到重新创建一个对象呢！！！
这样就不膈应了，而且代码好些多了！！！
菜狗菜狗！！！

新代码

class LinkedNode{
    int val;
    LinkedNode next;

    LinkedNode(){
        this.next=null;
    }
    LinkedNode(int val){
        this.val=val;
        this.next=null;
    }
}

class MyLinkedList {

    int length;

    LinkedNode linkedList;

    public MyLinkedList() {
        this.length=0;
        this.linkedList=null;
    }

    public int get(int index) {
        //先行条件
        if(index<0||index>=this.length||this.length==0)return -1;

        LinkedNode p=this.linkedList;
        //将指针移动到对应索引的节点
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        return p.val;
    }

    public void addAtHead(int val) {
        this.addAtIndex(0,val);
    }

    public void addAtTail(int val) {
        this.addAtIndex(this.length,val);
    }

    public void addAtIndex(int index, int val) {

        //先行条件
        if(index<0||index>this.length)return;


        LinkedNode newNode=new LinkedNode(val);
        //插在第一个节点之前特殊处理
        if(index==0){
            newNode.next=this.linkedList;
            this.linkedList=newNode;
            //链表长度加+1
            this.length++;
            return;
        }

        LinkedNode current=this.linkedList;

        int num=index-1;

        //移动到指定节点之前的位置
        while(num>0){
            current=current.next;
            num--;
        }
        newNode.next=current.next;
        current.next=newNode;

        //链表长度加+1
        this.length++;
    }

    public void deleteAtIndex(int index) {
        //先行条件
        if(index<0||index>=this.length||this.length==0)return;
        LinkedNode pre=null;
        LinkedNode current=this.linkedList;


        //如果删除的是首位索引，需要特殊处理
        if(index==0){
            this.linkedList=this.linkedList.next;
            this.length--;
            return;
        }

        //current指针和pre指针先行移动到指定位置
        while(index>0){
            pre=current;
            current=current.next;
            index--;
        }

        pre.next=current.next;

        //链表长度减一
        this.length--;
    }
}

别人的方法把addAtHead和addAtTail这俩方法都用addAtIndex来处理的，我怎么就只想到把addAtHead用addAtIndex处理呢，菜狗！