LeetCode - 707 设计链表 （设计）

单链表

注意 第一次添加节点 或者 addAtIndex（添加的节点在末尾）deleteAtIndex（删除了末尾的节点） 都有可能造成尾指针的变动 要进行判断并且更新尾指针

class MyLinkedList {
    
    class Node{
    
        int val;//节点的值
        Node next;//节点的next指针
        public Node(int val){
    
            this.val = val;
        }
    }
    private Node head;//头节点
    private Node tail;//尾节点
    public MyLinkedList() {
    
         head = new Node(0);//建立头节点 头节点不存储值 第一个值存储在头节点的next中
         tail = head;//尾指针指向头节点
    }
    
    public int get(int index) {
    
        // i 和 node要对应 i = 0 正好是head.next
        //头节点不存储值 第一个值存储在头节点的next中 
       int i = 0;
       Node node = head.next;
       //遍历寻找index对应节点
       while(i < index && node != null){
    
           node = node.next;
           i++;
       }
       //链表中存在index对应的节点
       if(node != null)//返回其值
          return node.val;
       else
          return -1;
    }
    
    public void addAtHead(int val) {
    
        //新建节点
         Node node = new Node(val);
        //将该节点插入头节点和头节点.next之间
         node.next = head.next;
         head.next = node; 
         //如果当前链表中只有一个节点
         //将尾指针指向该节点
         if(node.next == null)
            tail = node;
    }
    
    public void addAtTail(int val) {
    
        //新建节点
        Node node = new Node(val);
        //将其添加在尾节点之后
        tail.next = node;
        //此时该节点成为末尾节点 将尾指针指向它
        tail = node;
    }
    
    public void addAtIndex(int index, int val) {
    
        //寻找第index-1个节点
         int i = -1;
         Node node = head;
         while(i < index-1 && node != null){
    
             i++;
             node = node.next;
         }
         //如果存在第index-1个节点
         if(node != null)
         {
    
             //新建节点
             Node addNode = new Node(val);
             addNode.next = node.next;
             node.next = addNode;
             //注意可能添加到末尾更新tail
             if(addNode.next == null)
                 tail = addNode;
         }
         
    }
    
    public void deleteAtIndex(int index) {
    
        //寻找第index-1个节点
         int i = -1;
         Node node = head;
         while(i < index-1 && node != null){
    
             i++;
             node = node.next;
         }
         //存在第index-1个节点
         //并且其后还有第index个节点
         if(node != null && node.next!=null)
         {
    
             //删除第index个节点
            node.next = node.next.next;
            //可能删掉了最后一个节点
             if(node.next == null){
    
                tail = node;
            }
         }
    }
}

/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */