当前位置:   article > 正文

LeetCode 19. 删除链表的倒数第N个节点 C++解法_删除链表的倒数第n个节点c++完整代码

删除链表的倒数第n个节点c++完整代码

题目描述:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
题目地址:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

解答

此题关键点:

  • 遍历次数,使用双指针做出类似窗口的指向,两个指针分别指向窗口的左边和右边,最后窗口右边指向链表的尾结点,通过窗口左边指针删除指定节点。
  • 链表头结点与其他节点在删除时的不同处理,解决方法为在原链表上增加一个不用的头结点,使原来的头结点与后面的节点等价。这样做的另一个好处是所有原来的节点都有一个前节点,可以在算法中指向他们的前一个节点,方便删除的操作。不过需要注意返回值。
    代码及注释如下:
/**
 - Definition for singly-linked list.
 - struct ListNode {
 -     int val;
 -     ListNode *next;
 -     ListNode(int x) : val(x), next(NULL) {}
 - };
 */
class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode *tempHead = new ListNode(0);
		tempHead->next = head;
		ListNode *start = tempHead;	//窗口左边界
		ListNode *end = start;			//窗口右边界
		//使两个指针指向窗口的两个边
		for (int i = 0; i < n; i++, end = end->next);
		//找到窗口的位置
		for (; end->next != nullptr; start = start->next, end = end->next);
		start->next = start->next->next;
		return tempHead->next;		
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

在LeetCode中发现将头结点创建在堆区会使程序执行速度变快,所以使用智能指针头结点设置到堆区,使用智能指针让其退出方法时自动释放内存。代码如下:

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		//ListNode *tempHead = new ListNode(0);
		std::unique_ptr<ListNode> tempHead(new ListNode(0));
		tempHead->next = head;
		ListNode *start = tempHead.get();	//窗口左边界
		ListNode *end = start;			//窗口右边界
		//使两个指针指向窗口的两个边
		for (int i = 0; i < n; i++, end = end->next);
		//找到窗口的位置
		for (; end->next != nullptr; start = start->next, end = end->next);
		start->next = start->next->next;
		return tempHead->next;		
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

总结

  • 新增的头结点设置在栈区,这样可以避免内存泄漏,第二题也可以用这种方法避免内存泄漏,不过不知道为什么头结点设置在堆区会使程序执行速度更快。

  • 使用智能指针可以既创建在堆区,又避免内存泄漏,注意指针与智能指针之间的转换,使用tempHead.get(),而不是直接赋值。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/990713
推荐阅读
相关标签
  

闽ICP备14008679号