关于链表中虚拟头节点的使用介绍

2024-07-11 16:54| 来源: 网络整理| 查看: 265

在处理链表相关问题时,虚拟头节点是经常使用的一种方法,下面对于链表中虚拟头节点的使用举例作简要介绍.

以 leetcode 203. Remove Linked List Elements为例. 题目描述:Remove all elements from a linked list of integers that have value val.

Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5

第一反应想到的简单实现代码应该是:

忽略头节点处理的实现 class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* cur = head; while (cur->next != NULL) { if (cur->next->val == val) { ListNode* delNode = cur->next; cur->next = delNode->next; delete delNode; } else cur = cur->next; } return head; } };

很容易看出,这种实现存在问题.第一个问题是这种写法忽略了对于头节点的处理.考虑若头节点为空,while (cur->next != NULL)直接就会直接导致程序崩溃,所以对于头节点需要进行安全性的检查.第二个问题是删除逻辑的问题,如果删除的是头节点,上述代码种删除cur->next的逻辑是无法实现的,因为需要找到待删除节点的前驱.所以对于这种情况需要单独添加新的删除逻辑.

根据上述分析,我们可以修改得到以下实现.

考虑头节点处理的实现 class Solution { public: ListNode* removeElements(ListNode* head, int val) { if (head != NULL && head->val == val) { ListNode* delNode = head; head = delNode->next; delete delNode; } if (head == NULL) return NULL; ListNode* cur = head; while (cur->next != NULL) { if (cur->next->val == val) { ListNode* delNode = cur->next; cur->next = delNode->next; delete delNode; } else cur = cur->next; } return head; } };

上述实现解决了头节点的处理问题,可以看到,在处理的过程中需要避开很多陷阱,添加了一些繁琐的判断,整体代码也不够优美.那么有没有什么方法可以在处理头节点的情况下,保持程序逻辑的统一以及程序的简洁呢?这时候就要用到虚拟头节点的方法.

虚拟头节点其实比较容易理解,相当于在头节点前,加上一个虚拟的节点.这样,头节点就有了前驱,根据之前的分析,就可以简单地将删除节点的逻辑进行统一,实现如下

利用虚拟头节点的实现 class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while (cur->next != NULL) { if (cur->next->val == val) { ListNode* delNode = cur->next; cur->next = delNode->next; delete delNode; } else cur = cur->next; } ListNode* retNode = dummyHead->next; delete dummyHead; return retNode; } };

上述实现可以看出,利用虚拟头节点的方法,统一了整体操作的逻辑,避免了关于头节点繁琐的讨论和代码实现上的陷阱.除了上述例子以外,很多涉及链表的操作,我们都可以利用虚拟头节点的方法来进行统一简化逻辑的处理.

【本文地址】

关于链表中虚拟头节点的使用介绍

关于链表中虚拟头节点的使用介绍

今日新闻

推荐新闻