203.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：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 输出：[]

思路

随想录中使用两种方法移除链表元素。直接删除的方法如下。

2023.3.14补充：后续补充虚拟头节点的做法。假设一个虚拟头节点，指向head，通过虚拟头节点的不断移动来寻找相同的元素。此过程head没有变化。

做的过程中，直接删除的方法的难点在于：

  • 如何返回头节点。
  • 如何把元素从上一个节点链接到下一个节点。

C语言实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//法一 判断链表头结点是否为目标值，不是的话去掉
struct ListNode* removeElements(struct ListNode* head, int val) {
	typedef struct ListNode ListNode;
	ListNode* after = NULL;
	ListNode* cur;//构造一个参数，等于head
	while (head && head->val == val){//判断头节点是否有val值，有的话去掉
		ListNode* temp = head;
		head = head->next;
		free(temp);
	}
	cur = head;//一定是没有head值
	while (cur){//对cur进行操作，若为NULL，则说明已经遍历完节点
		after = cur->next;
		if (after && after->val == val){//要判断after是否存在
			cur->next = after->next;
            free(after);//删除节点
		}
		else{
			cur = cur->next;
		}
	}
	return head;
}

C++实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
	ListNode* removeElements(ListNode* head, int val) {
		ListNode* cur;
		ListNode* after;
		ListNode* temp;
		while (head && head->val == val){
			temp = head;
			head = head->next;
			delete temp;
		}
		cur = head;
		while (cur){
			after = cur->next;
			if (after && after->val == val){
				cur->next = after->next;
				delete after;
			}
			else{
				cur = cur->next;
			}
		}
		return head;
	}
};

使用虚拟头节点。。注意，使用虚拟头节点存储的头指针，在后续的指针操作中，若改变了链表中的头节点，虚拟头节点是始终指向链表的头结点的。

例如，虚拟头节点的next = head；

​ head由于临时指针（自己定义的一个指针，这个指针等于虚拟头节点，他们指向同一个位置）增删改变了，此时的next自动指向修改过后的head。

C语言实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode* removeElements(struct ListNode* head, int val) {
	typedef struct ListNode ListNode;
	ListNode* pre = (ListNode*)malloc(sizeof(ListNode));
    if (pre == NULL){//判断pre是否为空，若为空则直接返回报错。
		return pre;
	}
	pre->next = head;// point to head
	ListNode* cur = pre;
	while (cur->next){
		if (cur->next->val == val) {
			ListNode* temp = cur->next;
			cur->next = cur->next->next;
			free(temp);
		}
		else
		{
			cur = cur->next;
		}
	}
	head = pre->next;// delete old head ,pre will point new head auto.
	return head;
}