leetcode：203.移除链表元素（两种方法详解）网站首页 技术教程

leetcode：203.移除链表元素（两种方法详解）

Artiel 2024-06-14 17:18:18

简介leetcode：203.移除链表元素（两种方法详解）

前言：内容包括-题目，代码实现（两种方法），大致思路，代码解读

题目：

给你一个链表的头节点 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
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-linked-list-elements

代码实现1 原链表中删除

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
	struct ListNode* cur = head;
	while (cur)
	{
		if (cur->val == val)
		{
			if (prev == NULL)//删除的是第一个节点
			{
				cur = head->next;
				free(head);
				head = cur;
			}
			else//删除的是其他位置的节点
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}

大致思路：

prev指针用于指向链表每一个正在遍历的节点的前一个节点

遍历链表，若是当前节点的值！=val，遍历下一个节点

若是当前节点的值==val，删除这个节点，但是删除分为两种情况：

1 要删除的是链表的第一个节点

a 让cur指针遍历到下一个等待判断的节点（即第二个节点）

b 删除第一个节点

c 头指针head指向第二个节点

2 要删除的是除却第一个节点以外的其他节点

a 上一个节点prev指向被删除节点cur的下一个节点

b 删除节点

b 迭代，cur走向下一个等待判断的节点

代码实现2 尾插

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*cur = head;
    struct ListNode*rhead = NULL;//新链表
    struct ListNode*tail = NULL;
    while(cur)
    {
        if(cur->val!=val)//尾插
        {
           if(rhead==NULL)//链表为空时，尾插第一个元素，需要让rhead也指向这个被插入的元素
           {
               rhead = cur;
               tail = cur;
           }
           else//链表不为空 插入元素-->这个元素成为新的尾
           {
               tail->next = cur;
               tail = tail->next;
           }
           //插入完成后迭代，由于值为val的节点会被删除，所以每个尾节点的next都需要置空
           //cur和tail指向的是同一个节点，tail的next置空之前，需要让cur先走向下一个等待判断的节点，否则无法找到下一个等待判断的节点
           cur = cur->next;
           tail->next = NULL;
        }
        else//删除值为val的节点
        {
            struct ListNode*del = cur;//保存当前节点的地址
            cur = cur->next;//cur走向下一个等待判断的节点
            free(del);
        }
    }
    return rhead;
}