203. 移除链表元素

考点

• 链表的删除

题解

class Solution {
	public:
		ListNode* removeElements(ListNode* head, int val) {
			ListNode *dummyHead = new ListNode(-1, head), *cur = dummyHead;
			while(cur->next != nullptr){
				if(cur->next->val == val) cur->next = cur->next->next;
				else cur = cur->next;
			}
			return dummyHead->next;
		}
};

思路

单向链表中，当前节点无法知晓前一个节点的信息；如果增删改当前节点，上一个节点的next就得不到更新

所以每次操作的节点其实是当前节点的下一个

要保证操作的通用性，不用去判断操作头结点时的一些特殊情况；引入了dummyHead一个伪结点，它的next指向真正的头节点

（实际上，只要涉及到链表的操作，dummyHead几乎是必须的）

以序列{7, 4, 3, 7}为例，需要删除值为7的节点；从伪结点开始迭代

每次判断下一个节点的值是否满足题意；若是，则将当前节点的next指向下下个节点（将满足题意的节点从链表踢出）

若否，则指针移至下个节点，开启新一轮判断

由于核心问题就是不同情况下修改节点的next值，可以将其改造为递归

编写递归按照四部曲即可：

1. 子问题：更新自己的next值，需要下一个节点的信息

2. 递归语句顺序：递归方向分为一去一回，去方向至临界点后返回；本题应在回方向操作，因为要返回值给当前节点的上一个节点

   （当然也可以去方向操作，但那样和迭代无异，且无法处理头节点）

3. 返回值：如果当前节点要被删除，则返回它的next值；否则返回自己（本质上是返回应该存在于链表内的节点）

   临界点返回nullptr值，代表nullptr一定存在于链表内

4. 临界点：当前节点为nullptr

class Solution {
	public:
		ListNode* removeElements(ListNode* head, int val) {
			if(head == nullptr) return nullptr;
			head->next = removeElements(head->next, val);
			if(head->val == val) return head->next;
			return head;
		}
};