（链表）移除链表元素（双指针法）

文章目录

- 前言：
- 问题描述：
- 解题思路（双指针法）：
- 代码实现：
- 总结：

前言：

此篇是针对链表的经典练习题。

问题描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
示例 1：
在这里插入图片描述

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

解题思路（双指针法）：

1、设置两个均指向头节点的指针，pre（记录待删除节点的前一节点）和 cur (记录当前节点)；

2、遍历整个链表，查找节点值为 val 的节点，找到即删除该节点，否则继续查找。

① 找到，将当前节点的前一节点（之前最近一个值不等于 val 的节点(pre)）连接到当前节点（cur）的下一个节点（即将 pre 的下一节点指向 cur 的下一节点：pre->next = cur->next）。

② 没找到，更新最近一个值不等于 val 的节点（即 pre = cur），并继续遍历（cur = cur->next）。

这里以链表 1->2->6->3->4->5->6, val = 6 为例子，利用双指针进行删除操作如下：

在这里插入图片描述

代码实现：

struct ListNode* removeElements(struct ListNode* head, int 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 {
            pre = cur;
        }
        cur = cur->next;
    }
    return head;
}