【数据结构OJ题】移除链表元素

雨点打透心脏的1/2处 2023-10-12 21:54 47阅读 0赞

## **移除链表元素** ##

[原题链接：力扣][Link 1]

给你一个链表的头节点 `head` 和一个整数 `val` ，请你删除链表中所有满足 `Node.val == val` 的节点，并返回**新的头节点** 。

![65bf310c28c6429fb04df61c4155abba.png][]

**方法一：原地删除节点**

思路：

首先，定义两个指针：prve和cur。它们会在遍历链表的过程中分别指向当前节点的前一个节点和当前节点。初始情况下，prve指向NULL（因为当前节点是头结点），cur指向head。

![beabc16517fd45b5bfee719ebd4d99ca.png][]

然后，我们使用while循环遍历链表，直到cur指向NULL（也就是遍历完整个链表）。在每个节点处，我们判断当前节点（cur）的值是否等于val。如果是，我们就需要将该节点从链表中移除。

如果当前节点cur是头结点，那么我们需要特殊处理，因为头结点没有前一个节点。此时，我们修改head指向cur的下一个节点，然后释放cur所指向的内存空间，使得cur指向新的头结点（即head），继续遍历整个链表。

如果当前节点cur不是头结点，那么我们需要将cur从链表中移除。此时，我们将prve的next指针指向cur的下一个节点，然后释放cur所指向的内存空间，使得cur指向prve的下一个节点（也就是新的当前节点），继续遍历整个链表。

如果当前节点cur的值不等于val，我们就只需要更新prve和cur的指向，使得它们分别指向当前节点的前一个节点和当前节点的下一个节点，然后继续遍历整个链表。

具体过程图解：

![a6fa3af689ee44d18f83be65125c291c.png][]

**需要注意头节点的值是val的情况**

代码：

struct ListNode* removeElements(struct ListNode* head, int val)
    {
        //定义两个指针：prve和cur
        struct ListNode* prve = NULL;
        struct ListNode* cur = head;
    
        while (cur != NULL)
        {
            //判断当前节点（cur）的值是否等于val。如果是，我们就需要将该节点从链表中移除
            if (cur->val == val)
            {
                //如果当前节点cur是头结点，那么我们需要特殊处理
                if (cur == head)
                {
                    head = cur->next;
                    free(cur);
                    cur = head;
                }
                else
                {
                    prve->next = cur->next;
                    free(cur);
                    cur = prve->next;
                }
            }
            //如果当前节点cur的值不等于val，我们就只需要更新prve和cur的指向
            else
            {
                prve = cur;
                cur = cur->next;
            }
        }
        return head;
    }

**方法二：遍历链表，把不是val的节点拿出来进行尾插到新链表**

![2eca9c7d311348e0a93eb0fede8c4511.png][]

下面有两种方式来实现;

**不带哨兵卫头节点：**

struct ListNode* removeElements(struct ListNode* head, int val)
    {
        struct ListNode* tail = NULL;
        struct ListNode* cur = head;
        head = NULL;
        while (cur)
        {
            if (cur->val != val)
            {
                if (tail == NULL)
                {
                    head = tail = cur;
                }
                else
                {
                    tail->next = cur;
                    tail = cur;
                }
                cur = cur->next;
            }
            else
            {
                struct ListNode* del = cur;
                cur = cur->next;
                free(del);
            }
        }
        if (head)
        {
            tail->next = NULL;
        }
        return head;
    }

**带哨兵卫头节点：**

struct ListNode* removeElements(struct ListNode* head, int val)
    {
        struct ListNode* tail = NULL;
        struct ListNode* cur = head;
        head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
        head->next = NULL;
        while (cur)
        {
            if (cur->val != val)
            {
                tail->next = cur;
                tail = cur;
                cur = cur->next;
            }
            else
            {
                struct ListNode* del = cur;
                cur = cur->next;
                free(del);
            }
        }
        if (head)
        {
            tail->next = NULL;
        }          
        struct ListNode* del = head;
        head = head->next;
        free(del);
        return head;
    }

带哨兵卫头节点和不带哨兵卫头节点的方法类似。

[Link 1]: https://leetcode.cn/problems/remove-linked-list-elements/
[65bf310c28c6429fb04df61c4155abba.png]: https://img-blog.csdnimg.cn/65bf310c28c6429fb04df61c4155abba.png
[beabc16517fd45b5bfee719ebd4d99ca.png]: https://img-blog.csdnimg.cn/beabc16517fd45b5bfee719ebd4d99ca.png
[a6fa3af689ee44d18f83be65125c291c.png]: https://img-blog.csdnimg.cn/a6fa3af689ee44d18f83be65125c291c.png
[2eca9c7d311348e0a93eb0fede8c4511.png]: https://img-blog.csdnimg.cn/2eca9c7d311348e0a93eb0fede8c4511.png