哑节点的作用

2024-06-14 13:20| 来源: 网络整理| 查看: 265

哑节点的妙用哑节点

哑节点是在处理与链表相关的操作时，设置在链表头之前的指向链表头的节点，用于简化与链表头相关的操作。

ListNode dummy = new ListNode(0); dummy.next = head; //head是链表的头节点，dummy就是指向链表头部的哑节点。作用问题引入

在我刷leetcode时，遇到了删除链表的倒数第N个节点的问题。这个问题并不复杂，对于有一定编程经验的人来说，答题者很快就能想到使用双指针法来解决这一问题：两个指针都指向链表头部，然后一个指针先向后跳n个节点，然后两个指针同时沿链表向后跳，当第一个指针指向最后一个节点时，另外一个指针指向的就是需要被删除的节点。

初始代码

我很快就编写完成了如下代码：

class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode n1=head; ListNode n2=head; for(int i=0;i n1=n1.next; n2=n2.next; } n2.next=n2.next.next; return head; } }

对于普通的测试样例（即不涉及头尾操作的样例），这种写法都可以通过。

问题引入

但是当我面对操作头节点的问题时，代码就无法通过测试了。例如：我们一共有四个节点，需要删除倒数第四个节点。因为当我们删除了头节点的时候，我们用什么来返回链表呢？

哑节点妙用

在经过各种复杂的尝试之后，我还是解决了这个问题，一种方法是我需要定义更多的节点来指向各种各样的特殊位置，另一种方法就是不使用原链表，对原链表进行复制，逐个添加进新链表。这两种方法具体写起来都比较复杂。在看答案之后，我发现答案引入了哑节点，其实也就是在我最初的代码上进行很小的修改，就完美解决了问题：

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; }

上述代码作者：LeetCode 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/ 来源：力扣（LeetCode）以上代码就是在我的代码的基础上添加了dummy节点，用于指向head节点，完美解决了头节点的操作问题。

【本文地址】

公司简介

联系我们