【LeetCode】203. 移除链表元素（Remove Linked List Elements）

题目

要求：给你链表头结点head和整数val，删除链表中所有Node.val == val的节点，返回删除后的新头结点。

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

https://leetcode.cn/problems/remove-linked-list-elements/

思路

哑结点 dummy + 前驱指针 prev

• 当cur.val == val时（需要删除）：

  • prev.next = cur.next：让prev跳过cur，直接指向cur的下一个节点
  • cur = cur.next：cur移动到下一个节点（注意此时prev不动）

• 当cur.val != val时（保留）：

  • prev = cur：prev向前移动到cur的位置

  • cur = cur.next：cur向前移动

哑结点 dummy简介

哑结点（dummy/sentinel）就是在真正链表头前面，人为加一个“永远不删/不参与数据”的节点，它的next指向原来的head。

为什么要用它：统一删除逻辑。不管你删的是头结点、中间结点还是尾结点，都变成用前驱节点prev去改指针：prev.next = cur.next，不需要专门处理删头结点这种特例。

code

classSolution{publicListNoderemoveElements(ListNodehead,intval){ListNodedummy=newListNode(0,head);ListNodeprev=dummy,cur=head;while(cur!=null){//删除if(cur.val==val){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}returndummy.next;}}