image.png

解决思路

虚拟头结点

对于这样的链表，删除掉3
image.png
cur指针遍历链表，一旦遍历掉待删除元素的前一个，即cur.next 指向 3
image.png
记录下待删除的节点。然后将cur的next指针指向待删除节点的next节点
image.png
然后删除delNode
image.png
该逻辑对于删除最后一个元素依然适用
问题在于对于删除第一个元素是不使用的

第一个元素无法找到前一个指针，故无法删除

**设立一个虚拟的头结点 dummyHead
初始化的时候dummyHead的next指针指向真正的head

image.png
此时cur指针初始化的时候可以指向dummyHead
image.png
这样做之后，原来的头结点就有了前一个节点
此时从虚拟的dummyHead出发，对于链表中的所有头结点，删除的过程就可以统一了
最终返回dummyHead.next

  1. public ListNode removeElements(ListNode head, int val) {
  3.         //这里的dummyHead初始化的值并不重要，因为并不会被访问到
  4.         ListNode dummyHead = new ListNode(0);
  5.         //让dummyHead的next指向head
  6.         dummyHead.next = head;
  8.         ListNode cur = dummyHead;
  9.         while(cur.next!=null){
  10.             if(cur.next.val==val)
  11.                 cur.next = cur.next.next;
  12.             else
  13.                 cur = cur.next;
  14.         }
  15.         //最后放回的是虚拟头节点的next
  16.         return dummyHead.next;
  17.     }