【leetcode 203】移除链表元素

删除链表中等于给定值 val 的所有结点。

输入：1->2->6->3->4->5->6
输出：1->2->3->4->5

此题的关键问题要考虑链表头部结点判断问题，这里我采用的是从第二个元素开始依次判断，然后最终再比较头结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    // 特殊情况判断 容错处理
    if (head == NULL) return head;
    if (head->next == NULL) {
        if (head->val == val) {
            return NULL;
        } else {
            return head;
        }
    }
    struct ListNode *target = head;
    // 从第二个结点依次判断
    while (target->next) {
        if (target->next->val == val) {
            target->next = target->next->next;
        } else {
            target = target->next;
        }
    }
    // 判断头结点
    if (head->val == val) head = head->next;
    return head;
}

但是还有别的思路

添加虚拟头节点

由于我们对于头节点需要单独判断，我们也可以给当前链表添加一个虚拟头结点，然后就可以不用考虑头结点的问题了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    if (head == NULL) return head;
    struct ListNode *addNode = (struct ListNode*) malloc(sizeof(struct ListNode));
    addNode->val = val-1;
    addNode = head;
    head = addNode;
    struct ListNode *target = head;
    while (target->next) {
        if (target->next->val == val) {
            target->next = target->next->next;
        } else {
            target = target->next;
        }
    }
    if (head->val == val) head = head->next;
    return head;
}

递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    if (head == NULL) return NULL;
    head->next = removeElements(head->next,val);
    if (head->val == val) {
        return head->next;
    } else {
        return head;
    }
}