本系列博客为个人刷题思路分享，有需要借鉴即可。
注：部分思路借鉴自程序员小熊
链接：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; }
思路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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
完。
