删除链表的节点

简介: 删除链表的节点

剑指 Offer 18. 删除链表的节点

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

这是leetcode上的一个题

示例 1:


输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:


输入: head = [4,5,1,9], val = 1

输出: [4,5,9]

解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

解题思路

结构图大体如下

我们可以定义一个新链表newHead来存储与val不同的值 ,将与val值不同的节点尾插到新链表,但是没次尾插一个节点都需要找尾,我们再定义一个tail指针来帮助我们尾插,这样就简单很多了。

我们假设储存的四个值是 4 5 1 9

要删除的值是 1

我们大概来看一下思路

这里我们可以发现 我们找到要删除的值的时候

这个时候我们需要做三件事

第一 将前面的next指向被删除下面一个结构体的指针

第二 释放cur的位置

第三 cur前面的位置指向下面一个结构体的位置

那么如果说像现在的这种情况 后面没有要删除的值了 就可以一直cur指向下一个位置

那么我们想想看 指向什么位置才可以结束呢?

我们可以发现 当cur指向空的时候 循环条件就可以结束了

当然 这里有一个特殊情况

就是如果说 第一个值就是我们要找的值

这个时候pre指向的还是空指针

这里我们就要用到头删


这里我们还需要定义一个del来表示cur的下一个位置,防止我们释放cur的时候出现野指针问题

直接看代码:

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* newHead = NULL, * tail = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val != val)
        {
            if (tail == NULL)
            {
                newHead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if (tail)
        tail->next = NULL;
    return newHead;
}

这里还有一个问题,当最后一个节点是与val相同的值,释放掉以后tail指向也会出现野指针的问题,所以我们加上这句判断


 if (tail)
 tail->next = NULL;


整个代码就完整了,不会出现错误了

以上便是本文所有内容,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
2月前
|
算法
【优选算法专栏】专题九:链表--------两两交换链表中的节点
【优选算法专栏】专题九:链表--------两两交换链表中的节点
25 0
|
2月前
|
存储 Python
链表中插入节点
链表中插入节点
|
2月前
|
存储 Python
删除链表节点详解
删除链表节点详解
|
22天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
2月前
|
存储 Python
链表中删除节点
链表中删除节点
|
2月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
39 6
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
30 1
|
1月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
1月前
|
存储 SQL 算法
|
1月前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】