自己的做法
算法思想
这题很简单，考的就是链表的基本操作。
设置两个指针：current和pre，分别代表当前节点和当前节点的前一个节点。初始时，current = head, pre = nullptr。
当current节点和val相等时，则pre节点指向current->next，即为删除了current。然后current指向pre->next，继续遍历。
但是需要考虑一种特殊情况，即头结点等于val，此时，令head = head->next，current = head。继续循环。
遍历结束，返回head。
算法实现
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
26
| class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *pre = nullptr, *current = head;
while (current != nullptr) {
if (current->val == val) {
if (pre == nullptr) {
head = head->next;
current = head;
} else {
pre->next = current->next;
current = pre->next;
}
} else {
pre = current;
current = current->next;
}
}
return head;
}
};
|
性能分析
时间复杂度：遍历链表，为O(n)。
空间复杂度：使用两个指针，为O(1)。
官方做法
哨兵结点
算法思想
这道题目，唯一可能稍微难一点的就是边界问题。
如果链表中间节点和给定val相等，问题很简单，令 该节点前一个节点的next等于该节点的next即可。
唯一麻烦的就是，如果开头一个或多个结点和val相等，则会稍复杂些。
可以使用哨兵节点来解决。
即： 创建一个哨兵节点sentinel作为头结点，并令sentinel->next = head。然后即可简化我自己的做法。不需要考虑头结点相等的特殊情况。
只要注意：返回值是sentinel->next。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *sentinel = new ListNode();
sentinel->next = head;
ListNode *pre = sentinel, *current = sentinel->next;
while (current != nullptr) {
if (current->val == val) {
pre->next = current->next;
current = pre->next;
} else {
pre = current;
current = current->next;
}
}
return sentinel->next;
}
};
|
性能分析
时间复杂度：O(n)。
空间复杂度：O(1)。
不解释。