203. 移除链表元素

LeetCode题目:链表递归

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

示例 1:

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

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

提示:

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

初始代码

/**
 * 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) {

    }
};

解题思路

递归

又是链表相关的递归题。意味着我们要用栈的思维,从链表的最后一个节点往前看。

最后一个节点的val可能相等,所以我们递归应该递归到链表最后的空节点NULL。递归到该节点时,将NULL返回给链表尾节点的next。这样如果链表中就一个节点,删除该节点后链表也能置空。

和用迭代法删节点一样,我们要删除B节点前,得有它的上一个节点的next。这样我们才能把A的next指针从指向B节点改为指向C节点。那么递归的时候也是一样,代码如下

head->next=removeElements(head->next,val);

递归到最后时需要判断是否等于给定的val,相等就将B->next作为返回值,返回给A->next,从而实现A的next指向B->next即C节点的操作。

完整代码

/**
 * 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;
        head->next=removeElements(head->next,val);
        if(head->val==val)
            return head->next;
        else
            return head;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x