算法(链表)——移除链表元素

算法(链表)——移除链表元素

文章目录

• • 1.题目实例
  • 2.解题思路
  • 3.代码实现
  • • 3.1未设置虚拟结点
    • 3.2设置虚拟结点

---

1.题目实例

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

示例1
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-linked-list-elements

2.解题思路

    要实现单向链表中元素的移除，其实很简单。如果要移除的结点不是头结点，那么只需要将需要移除的结点的前一个结点的指针，指向移除结点的指针指向的结点即可。

    此外，我们不能忘记将该被移除的结点所占用的内存释放掉。
    而如果我们所要删除的结点是头结点，那么就和移除普通结点的 *** 作不一样，我们要使新的头结点等于原头结点指针所指向的结点，并释放原头结点内存。当然，我们也可以设置一个虚拟的头结点，这样在 *** 作的时候，头结点的移除就和普通结点的移除没有什么两样了。

3.代码实现 3.1未设置虚拟结点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head != NULL && head->val == val)//移除所有符合条件的头结点
        {
            ListNode *tmp = head;//创建等于头结点的临时结点
            head = head->next;
            delete tmp;//释放原头结点内存
        }
        ListNode *cur = head;
        while(cur != NULL && cur->next != NULL)//移除普通结点
        {
            if(cur->next->val == val)
            {
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

3.2设置虚拟结点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummyHead = new ListNode(0);//设置一个虚拟头结点
        dummyHead->next = head;
        ListNode *cur = dummyHead;//虚拟头结点指向头结点
        while(cur->next != NULL)
        {
            if(cur->next->val == val)
            {
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp; 
            }
            else
            {
                cur = cur->next;
            }
        }
        return dummyHead->next;//返回头结点
        delete dummyHead; 
    }
};