1. 题目描述

problem link

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

2. 解题

非递归解法

常规思路，加一个dummyHead从而免于处理头节点为val的情况。

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* curr = dummyHead;

    while (curr->next) {
        if (curr->next->val == val) {
            curr->next = curr->next->next;
        }
        else {
            curr = curr->next;
        }    
    }

    return dummyHead->next;
}

递归解法

3行的递归解法，神奇。

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL) return NULL;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}