为什么链表算法题如此亲睐虚拟节点..........

用户11173787

发布于 2024-10-12 10:56:20

790

发布于 2024-10-12 10:56:20

文章被收录于专栏：破晓

引言

相信大家在做算法题的时候，会经常用到虚拟节点这个技巧。但是却不明白它会给我们带来多大的便利，今天我们利用几道算法题来分析一下。

如何使用？

我们定义的链表结构如下：

struct ListNode
{
	ListNode(int _val=0,struct ListNode*_next=nullptr)
		:val(val),next(_next)
	{}
	ListNode(int val=0)
		:val(val), next(nullptr)
	{}
	struct ListNode* next;
	int val;
};

当我们使用虚拟节点时：

ListNode dummy(-1);
ListNode* p = &dummy;
p->next = head;

即可

示例

示例一：删除链表中值为n的节点

值为n的节点具体在哪个位置是不确定的。

当头节点的val值为n时，如果等于则需要更新头节点为下一个节点。
如果这个节点是除头节点外的其他节点，则将该节点的前节点的next指向后节点。

所以我们需要根据这一节点所在位置，做不同的处理。

class Solution
{
	bool Find_delete(ListNode* head, int n)
	{
		if (head == nullptr)
			return false;
		if (head->val == n)
		{
			head->next = head;
		}
		else
		{
			ListNode* pre = head;
			ListNode* cur = head->next;
			while (cur)
			{
				if (cur->val == n)
				{
					pre->next = head->next;
					return true;
				}
				else
				{
					pre = cur;
					cur = cur->next;
				}
			}
		}
		return false;
	}
};

而当我们使用了虚拟节点：

创建一个虚拟头节点 dummyHead，将其 next 指针指向原链表的头节点 head。
从虚拟头节点开始遍历链表，判断当前节点的下一个节点是否等于 val，如果等于则更新- 当前节点的 next 指针为下一个节点的下一个节点。
最后返回虚拟头节点的下一个节点作为新的头节点。

class Solution
{
	bool Find_delete(ListNode* head, int n)
	{
		ListNode dummy(-1), * p = &dummy;
		dummy.next = head;
		ListNode* pre = p;
		ListNode* cur = p->next;
		while (cur)
		{
			if (cur->val == n)
			{
				pre->next = head->next;
				return true;
			}
			else
			{
				pre = cur;
				cur = cur->next;
			}
		}
		return false;
	}
};

示例二：链表的插入操作

问题描述： 题目给一个链表的头节点head和一个int类型的变量val。需要在链表头部插入一个值为 val 的新节点，并返回新的头节点。 不使用虚拟头节点

如果链表为空（头节点为 null），需要特殊处理，直接返回新节点作为头节点。
如果链表不为空，需要更新新节点的 next 指针指向原链表的头节点，并返回新节点作为新的头节点。

class Solution
{
	ListNode* insert(ListNode* head, int n)
	{
		if (head == nullptr)
		{
			head = new ListNode(n);
			
		}
		else
		{
			ListNode* node = new ListNode(n);
			node->next = head;
			head = node;
		}
		return head;
	}
};

使用头节点

创建一个虚拟头节点 dummyHead，其 next 指针指向原链表的头节点 head。
创建一个新节点 newNode，其值为 val。
将新节点的 next 指针指向虚拟头节点的下一个节点（即原链表的头节点）。
更新虚拟头节点的 next 指针指向新节点。
最后返回虚拟头节点的下一个节点作为新的头节点。

class Solution
{
	ListNode* insert(ListNode* head, int n)
	{
		ListNode dummy(-1), * p = &dummy;
		ListNode* node = new ListNode(n);
	
		node->next = p->next;
		p->next = node;
		return p->next;
	}
};

好处