麦包包网站建设的特点,wordpress建站好么,福州商城网站开发公司,深圳人才引进入户申请官网破阵子-晏殊 燕子欲归时节#xff0c;高楼昨夜西风。 求得人间成小会#xff0c;试把金尊傍菊丛。歌长粉面红。 斜日更穿帘幕#xff0c;微凉渐入梧桐。 多少襟情言不尽#xff0c;写向蛮笺曲调中。此情千万重。 目录
题目描述#xff1a;
思路分析#xff1a;
方法及… 破阵子-晏殊 燕子欲归时节高楼昨夜西风。 求得人间成小会试把金尊傍菊丛。歌长粉面红。 斜日更穿帘幕微凉渐入梧桐。 多少襟情言不尽写向蛮笺曲调中。此情千万重。 目录
题目描述
思路分析
方法及时间复杂度
法一 双指针(经典解法)
法二 计算链表长度(暴力解法)
法三 栈
法四 哈希表
法五 vector
个人总结 题目描述
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 19. 删除链表的倒数第 N 个结点 - 力扣LeetCode
思路分析
此题要求是删除倒数第N个结点那么主要的就是找到倒数第N个结点然后让该节点的前一个指向该结点的下一个。 那么这道题便有五种以上的解法核心就是找到要删的那个结点。
方法及时间复杂度
法一 双指针(经典解法)
定义两指针fasthead,slowhead。 fast先走n步然后fast跟slow同时走。 直到fast走到空此时slow 就到删除的结点。原理设链表长L快指针共走L步慢指针走L-n步。故此方法由法二得来。 由于这题是删除该结点这得需要删除结点的前继结点。所以让slow少走一步。可以直接开辟一个虚拟结点让slowdummy。 这样solw就可以到达删除结点的前一个结点了。然后像思路分析那样操作。代码如下
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummynew ListNode(0,head);ListNode* fasthead,*slowdummy;while(n--){fastfast-next;}while(fast){fastfast-next;slowslow-next;}slow-nextslow-next-next;ListNode* ansdummy-next;delete dummy;return ans;}
};
时间复杂度O(L)链表长度为L。
空间复杂度O(1)。 法二 计算链表长度(暴力解法)
遍历链表计算长度减去n就是正着数的个数注意的是如果长度L-n0就是头删了。代码如下
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {int count0;ListNode* curhead,*prehead;while(cur){count;curcur-next;}if(countn) return head-next;curhead;for(int i0;i(count-n)cur!nullptr;i){precur;curcur-next;}pre-nextcur-next;return head;}
};
时间复杂度O(L)链表长度为L。
空间复杂度O(1)。 法三 栈
根据栈的特点先进后出创建一个虚拟头节点防止空栈让所有结点入栈然后出栈n个结点此时栈顶元素就是要删除的结点的前一个。 代码如下
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummynew ListNode(0,head);stackListNode* st;ListNode* curdummy;while(cur){st.emplace(cur);curcur-next;}for(int i0;in;i){st.pop();}ListNode* prest.top();pre-nextpre-next-next;ListNode* ansdummy-next;delete dummy;return ans;}
}; 时间复杂度O(L)链表长度为L。
空间复杂度O(L)。为栈开销 法四 哈希表
主要思想是一样的查找到删除结点的前一个结点如果前一个没有结点就头删。
代码如下
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {unordered_mapint,ListNode* hash;ListNode *curhead;int i0;while(cur){hash.insert({i,cur});curcur-next;}int targeti-n;if(target0) return head-next;//target上一个位置的指针指向下一个ListNode* lefthash[target-1];left-nextleft-next-next;return head;}
};
时间复杂度O(L)链表长度为L哈希表查找也为O(L)。
空间复杂度O(L)。哈希表的开销。 法五 vector
与法四思路相同不多解释。
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {vectorListNode* ret;ListNode* curhead;while(cur){ret.emplace_back(cur);curcur-next;}int targetret.size()-n;if(target0) return head-next;ListNode* leftret[target-1];left-nextleft-next-next;return head;}
};
时间复杂度O(L)链表长度为L。
空间复杂度O(L)。 个人总结
大致思路就是找倒数第n个结点删除结点实现起来其实并不复杂可以还有更多的方法做这道题。
