第n個節(jié)點)
1. 題目給你一個鏈表刪除鏈表的倒數(shù)第n個結(jié)點并且返回鏈表的頭結(jié)點。示例 1輸入head [1,2,3,4,5], n 2輸出[1,2,3,5]示例 2輸入head [1], n 1輸出[]示例 3輸入head [1,2], n 1輸出[1]2. 題解2.1. 計算2.1.1. 核心思想鏈表只能向后遍歷不能直接訪問倒數(shù)位置沒有下標。 倒數(shù)第n個結(jié)點 ?正數(shù)第總長度 ? n 1 個結(jié)點。例鏈表[1,2,3,4,5]長度count5刪除倒數(shù)第 2 個 (4)count?n 5?2 3→ 正數(shù)第 3 個結(jié)點 (3)是待刪節(jié)點的前驅(qū)。 讓前驅(qū)結(jié)點的 next跳過待刪結(jié)點cur-next cur-next-next。2.1.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*curhead;intlen0;while(cur){len;curcur-next;}curdummy;// 走到待刪節(jié)點的前驅(qū)len-n步for(inti0;ilen-n;i){curcur-next;}ListNode*delcur-next;cur-nextcur-next-next;deletedel;ListNode*ansdummy-next;deletedummy;returnans;}};2.1.3. 復雜度時間復雜度O ( L ) O(L)O(L)L 是鏈表長度完整遍歷 2 次鏈表空間復雜度O ( 1 ) O(1)O(1)只用幾個指針、計數(shù)器變量2.2. 棧2.2.1. 核心思想棧后進先出。 把鏈表所有節(jié)點依次壓入棧中棧底是頭結(jié)點棧頂是尾結(jié)點。 彈出 n 個節(jié)點彈出的第 1 個就是要刪除的倒數(shù)第 n 個結(jié)點。 此時棧頂剩下的元素就是待刪節(jié)點的前驅(qū)結(jié)點。 然后修改前驅(qū)的 next跳過被刪除節(jié)點。邊界如果彈完 n 個之后棧為空說明要刪的是頭結(jié)點。2.2.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){stackListNode*st;ListNode*curhead;while(cur!nullptr){st.push(cur);curcur-next;}ListNode*delnullptr;for(inti0;in;i){delst.top();st.pop();}if(st.empty()){headhead-next;}else{ListNode*prest.top();pre-nextpre-next-next;}deletedel;returnhead;}};2.2.3. 復雜度時間復雜度O ( L ) O(L)O(L)L 鏈表長度。遍歷一次鏈表入棧再彈出 n 次。空間復雜度O ( L ) O(L)O(L)需要棧存儲全部鏈表節(jié)點。2.3. 雙指針2.3.1. 核心思想利用兩個指針保持固定間隔 n。 快指針先往前走n 步之后快慢指針同步一起往后走。 當快指針走到鏈表末尾 (nullptr) 時慢指針恰好落在待刪除節(jié)點的前驅(qū)結(jié)點。為什么可以這樣 倒數(shù)第 n 個節(jié)點距離鏈表末尾空指針的距離正好是 n。 讓快指針先拉開 n 的距離再同速前進快指針碰到底慢指針就定位到目標前驅(qū)。必須搭配dummy 虛擬頭結(jié)點規(guī)避刪除頭結(jié)點的特殊邊界。 如果不用 dummy刪除頭節(jié)點的情況要額外 if 判斷。2.3.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*fastdummy;ListNode*slowdummy;for(inti0;in;i){fastfast-next;}while(fast-next!nullptr){fastfast-next;slowslow-next;}ListNode*delslow-next;slow-nextslow-next-next;deletedel;ListNode*resdummy-next;deletedummy;returnres;}};2.3.3. 復雜度時間復雜度O ( L ) O(L)O(L)只遍歷鏈表一遍?？偣惨苿又羔?L 次空間復雜度O ( 1 ) O(1)O(1)僅幾個指針變量常數(shù)空間。2.4. 三種算法對比方法時間空間特點計數(shù)兩次遍歷O(L)O(1)直觀遍歷兩遍要處理頭結(jié)點邊界棧O(L)O(L)利用后進先出邏輯簡單額外占用內(nèi)存快慢指針O(L)O(1)一次遍歷雙指針距離差最優(yōu)3.19. 刪除鏈表的倒數(shù)第 N 個結(jié)點 - 力扣LeetCode hot100_刪除鏈表的倒數(shù)第n個節(jié)點
1. 題目給你一個鏈表刪除鏈表的倒數(shù)第n個結(jié)點并且返回鏈表的頭結(jié)點。示例 1輸入head [1,2,3,4,5], n 2輸出[1,2,3,5]示例 2輸入head [1], n 1輸出[]示例 3輸入head [1,2], n 1輸出[1]2. 題解2.1. 計算2.1.1. 核心思想鏈表只能向后遍歷不能直接訪問倒數(shù)位置沒有下標。 倒數(shù)第n個結(jié)點 ?正數(shù)第總長度 ? n 1 個結(jié)點。例鏈表[1,2,3,4,5]長度count5刪除倒數(shù)第 2 個 (4)count?n 5?2 3→ 正數(shù)第 3 個結(jié)點 (3)是待刪節(jié)點的前驅(qū)。 讓前驅(qū)結(jié)點的 next跳過待刪結(jié)點cur-next cur-next-next。2.1.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*curhead;intlen0;while(cur){len;curcur-next;}curdummy;// 走到待刪節(jié)點的前驅(qū)len-n步for(inti0;ilen-n;i){curcur-next;}ListNode*delcur-next;cur-nextcur-next-next;deletedel;ListNode*ansdummy-next;deletedummy;returnans;}};2.1.3. 復雜度時間復雜度O ( L ) O(L)O(L)L 是鏈表長度完整遍歷 2 次鏈表空間復雜度O ( 1 ) O(1)O(1)只用幾個指針、計數(shù)器變量2.2. 棧2.2.1. 核心思想棧后進先出。 把鏈表所有節(jié)點依次壓入棧中棧底是頭結(jié)點棧頂是尾結(jié)點。 彈出 n 個節(jié)點彈出的第 1 個就是要刪除的倒數(shù)第 n 個結(jié)點。 此時棧頂剩下的元素就是待刪節(jié)點的前驅(qū)結(jié)點。 然后修改前驅(qū)的 next跳過被刪除節(jié)點。邊界如果彈完 n 個之后棧為空說明要刪的是頭結(jié)點。2.2.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){stackListNode*st;ListNode*curhead;while(cur!nullptr){st.push(cur);curcur-next;}ListNode*delnullptr;for(inti0;in;i){delst.top();st.pop();}if(st.empty()){headhead-next;}else{ListNode*prest.top();pre-nextpre-next-next;}deletedel;returnhead;}};2.2.3. 復雜度時間復雜度O ( L ) O(L)O(L)L 鏈表長度。遍歷一次鏈表入棧再彈出 n 次。空間復雜度O ( L ) O(L)O(L)需要棧存儲全部鏈表節(jié)點。2.3. 雙指針2.3.1. 核心思想利用兩個指針保持固定間隔 n。 快指針先往前走n 步之后快慢指針同步一起往后走。 當快指針走到鏈表末尾 (nullptr) 時慢指針恰好落在待刪除節(jié)點的前驅(qū)結(jié)點。為什么可以這樣 倒數(shù)第 n 個節(jié)點距離鏈表末尾空指針的距離正好是 n。 讓快指針先拉開 n 的距離再同速前進快指針碰到底慢指針就定位到目標前驅(qū)。必須搭配dummy 虛擬頭結(jié)點規(guī)避刪除頭結(jié)點的特殊邊界。 如果不用 dummy刪除頭節(jié)點的情況要額外 if 判斷。2.3.2. 代碼/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*fastdummy;ListNode*slowdummy;for(inti0;in;i){fastfast-next;}while(fast-next!nullptr){fastfast-next;slowslow-next;}ListNode*delslow-next;slow-nextslow-next-next;deletedel;ListNode*resdummy-next;deletedummy;returnres;}};2.3.3. 復雜度時間復雜度O ( L ) O(L)O(L)只遍歷鏈表一遍?？偣惨苿又羔?L 次空間復雜度O ( 1 ) O(1)O(1)僅幾個指針變量常數(shù)空間。2.4. 三種算法對比方法時間空間特點計數(shù)兩次遍歷O(L)O(1)直觀遍歷兩遍要處理頭結(jié)點邊界棧O(L)O(L)利用后進先出邏輯簡單額外占用內(nèi)存快慢指針O(L)O(1)一次遍歷雙指針距離差最優(yōu)3.19. 刪除鏈表的倒數(shù)第 N 個結(jié)點 - 力扣LeetCode