[数据结构与算法]LeetCode 203. 移除链表元素 （C语言）

LeetCode 203. 移除链表元素

1.题目描述

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

2.思路

本题的大致思路是，设置两个指针p1，p2，初始分别指向头节点以及头节点的下一个节点，然后依次遍历链表，如果遇到相等的值，就删除p2指向的节点，然后p2向后移动，p1保持不动，直到p1与p2所指节点的值不同，此时p1，p2均向后移动。但是由题目样例的示例三我们可以看到，如果一个链表的n个节点的值均相等，按照上述思路，我们最后的结果仍会有一个元素剩余，上述思路只能解决链表中的值至少有两个不同i时的情况，所以我们可以对链表先进行处理，去掉前n个值相等的连续节点，使当前节点与下一节点的值不同，再通过上述思路，设置p1，p2，指针，遍历至链表末尾即可。

3. 代码

struct ListNode* removeElements(struct ListNode* head, int val){
    // 若链表本来就为NULL.直接返回head
    if (head == NULL) return head;

    // // 消除链表连续前n个值为val的结点
    do {
        if (head->val == val)  head = head->next;
        else break;
    }
    while (head != NULL);
    if (head == NULL) return head;   // 此时如果链表为空 直接返回

    // 处理后续情况
    struct ListNode *p = head;
    struct ListNode *pf = head->next;
    while (pf != NULL) {
        if (pf->val == val) {
            p->next = pf->next;
            pf = pf->next;
        }
        else {
            p = p->next;
            pf = pf->next;
        }
    }
    return head;
}