建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請聯(lián)系三分鐘學(xué)前端公眾號。
創(chuàng)新互聯(lián)公司主要業(yè)務(wù)有網(wǎng)站營銷策劃、成都網(wǎng)站建設(shè)、成都做網(wǎng)站、微信公眾號開發(fā)、小程序設(shè)計(jì)、HTML5、程序開發(fā)等業(yè)務(wù)。一次合作終身朋友，是我們奉行的宗旨；我們不僅僅把客戶當(dāng)客戶，還把客戶視為我們的合作伙伴，在開展業(yè)務(wù)的過程中，公司還積累了豐富的行業(yè)經(jīng)驗(yàn)、營銷型網(wǎng)站建設(shè)資源和合作伙伴關(guān)系資源，并逐漸建立起規(guī)范的客戶服務(wù)和保障體系。
給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例：
- 給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
- 當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?nbsp;1->2->3->5.
說明：
給定的 n 保證是有效的。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎?
解法：快慢指針
解題思路： 需要?jiǎng)h除鏈表中的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，我們需要知道的就是倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，然后刪除刪除倒數(shù)第 n+1 節(jié)點(diǎn)的后繼節(jié)點(diǎn)即可
步驟：
使用 2 個(gè)指針：
- fast 快指針提前走 n+1 步
- slow 指針指向當(dāng)前距離 fast 倒數(shù)第 n 個(gè)節(jié)點(diǎn)， 初始為 head
然后， fast 、 slow 同步向前走，直到 fast.next 為 null
此時(shí)，fast 為最后一個(gè)節(jié)點(diǎn)，slow 就是倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，此時(shí)問題就變更為刪除鏈表中的 slow 的后繼節(jié)點(diǎn)
但存在一個(gè)問題，當(dāng)鏈表長度為 n 時(shí)，fast 是前進(jìn)不到 n+1 個(gè)節(jié)點(diǎn)位置的，所以此時(shí)有兩種解決思路：
- 創(chuàng)建一個(gè)頭節(jié)點(diǎn) preHead ，設(shè)置 preHead.next = head ，這樣就可以解決以上問題，刪除倒數(shù)第 n 個(gè)節(jié)點(diǎn)后，返回的 preHead.next 即可
- 另外一種是，fast 快指針提前走 n 步后，判斷 fast.next 是否為 null ，即 fast 是否是最后一個(gè)節(jié)點(diǎn)，如果是，則 head 為倒數(shù)第 n 個(gè)節(jié)點(diǎn)，此時(shí)問題可以簡化為刪除頭節(jié)點(diǎn);如果不是， fast = fast.next ，fast 再前進(jìn)一步，slow 為倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，也解決了以上問題。
解決方案一：添加 preHead 節(jié)點(diǎn)
- const removeNthFromEnd = function(head, n) {
- let preHead = new ListNode(0)
- preHead.next = head
- let fast = preHead, slow = preHead
- // 快先走 n+1 步
- while(n--) {
- fast = fast.next
- }
- // fast、slow 一起前進(jìn)
- while(fast && fast.next) {
- fast = fast.next
- slow = slow.next
- }
- slow.next = slow.next.next
- return preHead.next
- };
解決方案二：單獨(dú)處理倒數(shù)第 n 節(jié)點(diǎn)
- const removeNthFromEnd = function(head, n) {
- let fast = head, slow = head
- // 快先走 n 步
- while(--n) {
- fast = fast.next
- }
- if(!fast.next) return head.next
- fast = fast.next
- // fast、slow 一起前進(jìn)
- while(fast && fast.next) {
- fast = fast.next
- slow = slow.next
- }
- slow.next = slow.next.next
- return head
- };
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
來源：https://github.com/sisterAn/JavaScript-Algorithms
網(wǎng)站名稱：每日：刪除鏈表倒數(shù)第N個(gè)結(jié)點(diǎn)
當(dāng)前鏈接：http://www.dlmjj.cn/article/ccoeggg.html
