本系列博客为个人刷题思路分享，有需要借鉴即可。
注：部分思路借鉴自程序员小熊
链接：https://leetcode.cn/problems/remove-linked-list-elements/solutions/341875/203-yi-chu-lian-biao-yuan-su-you-ya-di-gui-c-yu-ya/
来源：力扣（LeetCode）
1.目录大纲：
2.题目链接：
T1：LINK
3.详解思路：
T1:
思路1：双指针：遍历原链表，遇到val就执行删除val节点的操作
分析1：时间复杂度：O(N) 结论：yes
struct ListNode* removeElements(struct ListNode* head, int val){
//处理head == val 的情况，使head！=val
while (NULL != head && head->val == val)
{
head = head->next;
}
struct ListNode* cur = head;
struct ListNode* pre = head;
while (cur != NULL) {
if (cur->val == val) {
//跳跃
pre->next = cur->next;
} else {
//下一个跟进cur
pre = cur;
}
//cur不断向前走
cur = cur->next;
}
return head;
}
当然上面所说的思路也可以这样写：
struct ListNode* removeElements(struct ListNode* head, int val){
//处理*head == val 的情况，使*head！=val
while (NULL != head && head->val == val)
{
head = head->next;
}
if(head == NULL)
{
return NULL;
}
struct ListNode* cur = head->next;//如果head为空链表这样写不合法
struct ListNode* pre = head;
while (cur != NULL) {
if (cur->val == val) {
//跳跃
pre->next = cur->next;
} else {
//下一个跟进cur
pre = cur;
}
//cur不断向前走
cur = cur->next;
}
return head;
}
思路2:虚拟哨兵
分析：时间复杂度：O(N) 结论：yes
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode* cur = dummyHead;
while (cur->next != NULL) {
if (cur->next->val == val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return dummyHead->next;
}
作者：程序员小熊
链接：https://leetcode.cn/problems/remove-linked-list-elements/solutions/341875/203-yi-chu-lian-biao-yuan-su-you-ya-di-gui-c-yu-ya/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路3：重新构造一个新链表
分析3：时间复杂度：O(N) OK
struct ListNode* removeElements(struct ListNode* head, int val){
//定义新链表的头尾指针
struct ListNode* newHead = NULL;
struct ListNode* newTail = NULL;
//
struct ListNode* pcur = head;
while(pcur)
{
//不是val，尾插到新链表
if(pcur->val!=val)
{
if(newHead == NULL)
{
//链表为空
newHead = newTail = pcur;
}
else//链表不为空
{
newTail->next = pcur;
newTail = newTail->next;//更新尾节点
}
}
//更新pcur指针
pcur = pcur->next;
}
//加上null
if(newTail)
{
newTail->next = NULL;
}
//返回
return newHead;
}
思路4：单指针法
思路分析4：yes
struct ListNode* removeElements(struct ListNode* head, int val){
while (NULL != head && head->val == val) {
head = head->next;
}
if (NULL == head) {
return head;
}
struct ListNode* pre = head;
while (pre->next != NULL) {
//找到值为 val 的节点，并将其删除
if (pre->next->val == val) {
pre->next = pre->next->next;
} else {
//继续遍历
pre = pre->next;
}
}
return head;
}
作者：程序员小熊
链接：https://leetcode.cn/problems/remove-linked-list-elements/solutions/341875/203-yi-chu-lian-biao-yuan-su-you-ya-di-gui-c-yu-ya/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路5：递归
思路分析5：可行。
struct ListNode* removeElements(struct ListNode* head, int val){
//递归指向NULL时候终止，开始回归
if (NULL == head) {
return head;
}
//递归结果暂时存储
head->next = removeElements(head->next, val);
//三目操作符简化
return head->val == val ? head->next : head;
}
struct ListNode* removeElements(struct ListNode* head, int val){
if (NULL == head) {
return head;
}
/* 删除头节点后所有值为 val 的节点 */
struct ListNode* res = removeElements(head->next, val);
/* 头节点是待删除的节点 */
if (head->val == val) {
return res;
/* 头节点不是待删除的节点，头节点后面挂接已处理的链表（更短的） */
} else {
head->next = res;
return head;
}
}
作者：程序员小熊
链接：https://leetcode.cn/problems/remove-linked-list-elements/solutions/341875/203-yi-chu-lian-biao-yuan-su-you-ya-di-gui-c-yu-ya/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
完。
