C/C++教程

【Leetcode数据结构算法题】203. 移除链表元素(链表篇)

本文主要是介绍【Leetcode数据结构算法题】203. 移除链表元素(链表篇),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目内容:

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

在这里插入图片描述
leetcode题目链接(点击即可跳转)


思路分析

这是一个比较简单的单链表题目,属于单向不带头非循环链表。要注意这里的头节点不是带头结点的那种“头结点”。这里的头节点相当于链表的名字(巨坑)。
虽然题目本身难度系数不大,但是如果不细心分析清楚,一看到题目就立马编程,那么调试的时候可能会耗费挺多时间的。
实际上,对于链表相关的题目,不管难易程度如何,我们都应该先画图去分析,因为这类题目通常会涉及到多种条件,而这些条件往往就是我们编程的时候需要特别注意的地方。
以本题为例:
情况一:有多个有效结点的正常场景

假设创建一个指针cur,cur首先指向head。然后cur往后走,去寻找值 = val的结点,当cur找到对应的结点后,我们这时候想要删除这个结点,却发现这是一个单链表,cur前面一个结点我们此时并不知道。如果说我们这时候又想从头开始去遍历链表找到cur前面一个结点,就会显得很“麻烦”。
这个时候我们就应该想到,一开始,我们可能就需要创建两个指针。一个用来遍历链表找值为val的结点,另外一个则是当找到对应结点时可以找到该结点的上一个结点,完成删除结点的操作。
在这里插入图片描述

情况二:仅有一个有效结点的特殊场景
在这里插入图片描述

可以看到情况一中使用的方法无法成功解决仅有一个有效结点(且该节点值恰好为val)的情况。所以实际编程过程中,要将情况一和情况二分开讨论。(当然,这里之所以要分开讨论情况一、情况二,是因为有很多链表的题目中这两种情况下处理的方式都不相同,培养这样的思维可以有效的帮助我们分析以及减少犯错。)

情况三:空链表的极端场景
在这里插入图片描述

当链表中仅有头结点时,我们应该直接返回,不需要进行任何处理。由此可知,这种情况判断的优先级最高,一开始我们就需要判断。


函数接口实现

/**
 * 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* prev = NULL;
    struct ListNode* cur = head;
    //cur遍历链表
    while(cur){
        //cur指向的结点值不为val时,cur往后走
        while(cur && (cur->val != val)){
            prev = cur;//将当前结点的位置给prev
            cur = cur->next;//cur走向下一个结点
        }
        if(cur == head){//删除的结点是头节点指向的结点
            head = head->next;//头节点指向的位置向后移动
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
        else if(cur){//删除的结点不是头节点指向的结点且cur不为空
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
            prev->next = cur;
        }
    }
    return head;
}

在这里插入图片描述

这篇关于【Leetcode数据结构算法题】203. 移除链表元素(链表篇)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!