结点的定义：

class Node {    int val;    Node next;  //构造方法    public Node(int val) { this.val = val;    }    public Node(int val, Node next) { this.val = val; this.next = next;    }    public Node() {    }}

无头链表的删除

准备工作：

public class SingleLinkedList {  //创建一个head引用，用于存储头结点的地址    private Node head;    private int size;//存储结点个数}

无头链表中最麻烦的一点就是头结点需要我们特殊处理，因为除了头结点外的结点都有前驱，而头结点没有前驱，因此需要单独考虑

删除链表中索引为index位置的结点

index从0开始计算

public void removeIndex(int index){  if(head == null){    //如果没有链表为空，则直接返回    System.out.println("LinkedList is empty");    return;  }  //判断index的合法性  if(index < 0 || index >= size){    System.out.println("remove index illegal");    return;  }  if(index == 0){    //如果是删除头结点    Node node = head;//保存头结点    head = head.next;    node.next = null;//断开被删除结点的next    size--;  }else{    //不是删除头结点    Node prev = head;    for(int i = 0; i< index - 1; i++){      //从头结点开始，走index-1步到达被删除结点的前驱      prev = prev.next;    }    Node node = prev.next;    prev.next = node.next;//让前驱结点指向下下个结点    node.next = null;    size--;  }}

删除链表中第一个元素值为val的结点

我们依然要单独查看第一个结点是否是我们要删除的元素，如果是的话，单独删除

public void removeValOnce(int val){  if(head == null){    //如果没有链表为空，则直接返回    System.out.println("LinkedList is empty");    return;  }  //如果第一个结点就是待删除结点  if(head.data = val){    Node node = head;    head = head.next;    node.next = null;    size--;  }else{    //如果第一个结点不是待删除结点    Node prev = head;    while(prev.next != null){      if(prev.next.val == val){ Node node = prev.next; prev.next = node.next; node.next = null; size--; return;      }      prev = prev.next;    }  }}

删除链表中所有元素值为val的结点

这里值得注意的是：如果头结点元素是待删除结点，删除之后，还需要判断删除后新的头结点是否还是待删除元素，也就是说，不能删除一次head后就走到新的头结点的后继结点

对于头结点以外的删除，我们需要判断前驱结点的后一个结点被删除后，新结点是否还是待删除结点，因此只有当结点不是待删除元素的情况下，前驱结点才能后移

public void removeValAll(int val){  if(head == null){    //如果没有链表为空，则直接返回    System.out.println("LinkedList is empty");    return;  }  //头结点的删除  while(head != null && head.val == val){    Node node = head;    head = head.next;    node.next = null;    size--;  }  if(head == null){    //此时链表已经被删完了    return;  }  Node prev = head;  while(prev.next != null){    //判断下一个元素是否为待删除元素    if(prev.next.val == val){      //删除该元素      Node node = prev.next;      prev.next = node.next;      node.next = null;      size--;      //删除后prev不向后走，否则当前prev的下一个元素会因为没有前驱而再也无法删除了    }else{      //仅当下一个元素不为待删除元素时向后走      prev = prev.next;    }  }}

带头链表的删除

从前面的无头单链表的删除来看，我们每一次删除都要单独判断头结点是否为待删除结点

实际上，我们可以引入一个虚拟头结点，该结点只存储了头结点的地址，而不存储元素值，这样一来，对链表的操作来说，每一个结点都带有前驱结点，不再需要为头结点单独考虑

准备工作：

//创建虚拟头结点Node dummyHead = new Node();int size = 0;//存储结点个数

删除链表中索引为index位置的结点

public void remove(int index){    if(dummyHead.next == null){      //判断链表是否为空 System.out.println("LinkedList is empty"); return;    }    if(index < 0 || index >= size){      //判断index的合法性 System.out.println("remove index illegal"); return;    }    Node prev = dummyHead;    for (int i = 0; i < index; i++) {      //让prev一直走到待删除元素的前驱 prev = prev.next;    }  //删除结点    Node node = prev.next;    prev.next = node.next;    node.next = null;    size--;}

删除链表中第一个元素值为val的结点

public void removeValOnce(int val){    if(dummyHead.next == null){      //判断链表是否为空 System.out.println("LinkedList is empty"); return;    }    Node prev = dummyHead;    while(prev.next != null){ if(prev.next.val == val){   //找到待删除元素，并删除     Node node = prev.next;     prev.next = node.next;     node.next = null;     size--;     return; }      //如果该结点不是待删除元素，则向后走 prev = prev.next;    }    System.out.println("val does not exist");}

删除链表中所有元素值为val的结点

public void removeValAll(int val){    if(size == 0){ System.out.println("LinkedList is empty"); return;    }    Node prev = dummyHead;    while(prev.next != null){      //为了保证删除一个结点后的下一个结点还是待删除元素      //只有在该结点不为val的时候向后移动，否则不动 if(prev.next.val == val){     Node node = prev.next;     prev.next = node.next;     node.next = null;     size--; }else{     prev = prev.next; }    }}

KTV音响网