设计链表-单链表

//单链表
class ListNode{
  int val;
  ListNode next;
  ListNode(){}
  ListNode(int val){
	this.val=val;
  }
}
class MyLinkedList{
  //size存储链表元素的个数
  int size;
  //虚拟头节点
  ListNode head;
  //初始化链表
  public MyLinkedList(){
  	size=0;
	head=new ListNode(0);
  }
  //获取第index个节点的数值,注意index是从0开始的,第0个节点就是头节点
  public int get(int index){
  	//如果index非法,返回-1
	if(index<0||index>=size){
		return -1;
	}
	ListNode cur=head;
	//包含一个虚拟头节点,所以查找第index+1个节点
	for(int i=0;i<=index;i++){
		cur=cur.next;
	}
	return cur.val;
  }
  //在链表第index个节点之前插入一个节点
  public void addAtIndex(int index,int val){
	if(index>size){
		return;
	}
	if(index<0){
	  index=0;
	}
	size++;
	//找到要插入节点的前驱
	ListNode pred=head;
	for(int i=0;i<index;i++){
	  pred=pred.next;
	}
	ListNode toAdd=new ListNode(val);
	toAdd.next=pred.next;//要让新节点先指向前驱节点的后一个节点
	pred.next=toAdd;
	//在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
  //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
	    return;
        }
        ListNode pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}