【数据结构】移除链表元素-图文解析（单链表OJ题）

这篇具有很好参考价值的文章主要介绍了【数据结构】移除链表元素-图文解析（单链表OJ题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】移除链表元素-图文解析（单链表OJ题）,数据结构,数据结构,链表,c语言

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

本文导航

💭做题思路

🎨画图更好理解：

✍️代码实现

🗂️分情况讨论：

❄️极端情况：

💭做题思路

遍历链表，找到值为 val 的节点删除

这里需要两个指针

cur 用来遍历链表

prev 指向 cur 的前一个位置，方便删除一个节点后，链接前后节点

如果遇到要删除的节点，就让 prev->next = cur->next

注：不要忘了 free 删除掉的节点

🎨画图更好理解：

【数据结构】移除链表元素-图文解析（单链表OJ题）,数据结构,数据结构,链表,c语言

✍️代码实现

🗂️分情况讨论：

1. 当 cur->val == val 时，删除该节点

（1）头删要单独处理，因为头删会改变 head 的指向，本题要求返回新的头节点

（2）剩下的正常处理

2. 当 cur->val != val 时，让 prev 和 cur 指向下一个节点

最后，当 cur == NULL 时，说明此链表已经全部遍历完毕，结束循环遍历。

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    //当cur == NULL时结束循环
    while (cur != NULL)
    {
        if (cur->val == val)//删除
        {
            if (cur == head)
            {
                //头删
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                //正常删
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else//指向下一个
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}