移除链表元素

发布时间:2024年01月01日

description

给你一个链表的头节点 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

idea

注意该链表中的“头结点”是存储数据的

  • 增加辅助的“头结点”,把链表的所有结点一同判断,最后直接去辅助“头结点”的next即可
  • 对头结点的数值情况进行相应处理

solution1(迭代)

判断首个结点数值的不同情况

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

加个辅助的头结点(哑结点)

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

solution2(递归)

代码很优雅,效率很不体面~

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == NULL) return head;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};
文章来源:https://blog.csdn.net/Moliay/article/details/135329113
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。