移除链表元素

Trace

6.5 每日一题

传送门：https://leetcode-cn.com/problems/remove-linked-list-elements/

Problem

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

方法一（直接删）：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {  
        if(head==NULL) return NULL;
        ListNode* p=head;
        ListNode* q=head->next;
        while(q!=NULL){
            if(q->val==val){
                p->next=q->next;
                q=p->next;
            }
            else{
                p=p->next;
                q=q->next;
            }
        }
        if(head->val==val) head=head->next;
        return head;
    }
};

删除结点需要知道被删除节点前面的节点，所以多用了一个$ListNode$。

方法二（递归）：

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