赞
踩
题目描述:给定一个链表,删除链表的倒数第 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; } };
在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; } };
新增的头结点设置在栈区,这样可以避免内存泄漏,第二题也可以用这种方法避免内存泄漏,不过不知道为什么头结点设置在堆区会使程序执行速度更快。
使用智能指针可以既创建在堆区,又避免内存泄漏,注意指针与智能指针之间的转换,使用tempHead.get(),而不是直接赋值。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。