日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網營銷解決方案
每日：刪除鏈表倒數第N個結點

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯(lián)系三分鐘學前端公眾號。

創(chuàng)新互聯(lián)公司主要業(yè)務有網站營銷策劃、成都網站建設、成都做網站、微信公眾號開發(fā)、小程序設計、HTML5、程序開發(fā)等業(yè)務。一次合作終身朋友，是我們奉行的宗旨；我們不僅僅把客戶當客戶，還把客戶視為我們的合作伙伴，在開展業(yè)務的過程中，公司還積累了豐富的行業(yè)經驗、營銷型網站建設資源和合作伙伴關系資源，并逐漸建立起規(guī)范的客戶服務和保障體系。 

給定一個鏈表，刪除鏈表的倒數第 n 個節(jié)點，并且返回鏈表的頭結點。

示例：

 
 
 
    
  
  
  
  1. 給定一個鏈表: 1->2->3->4->5, 和 n = 2. 
    2. 
  
  
  
  2. 當刪除了倒數第二個節(jié)點后，鏈表變?yōu)?nbsp;1->2->3->5. 
    3.

說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現嗎?

解法：快慢指針

解題思路： 需要刪除鏈表中的倒數第 n 個節(jié)點，我們需要知道的就是倒數第 n+1 個節(jié)點，然后刪除刪除倒數第 n+1 節(jié)點的后繼節(jié)點即可

步驟：

使用 2 個指針：

  • fast 快指針提前走 n+1 步
  • slow 指針指向當前距離 fast 倒數第 n 個節(jié)點， 初始為 head

然后， fast 、 slow 同步向前走，直到 fast.next 為 null

此時，fast 為最后一個節(jié)點，slow 就是倒數第 n+1 個節(jié)點，此時問題就變更為刪除鏈表中的 slow 的后繼節(jié)點

但存在一個問題，當鏈表長度為 n 時，fast 是前進不到 n+1 個節(jié)點位置的，所以此時有兩種解決思路：

  • 創(chuàng)建一個頭節(jié)點 preHead ，設置 preHead.next = head ，這樣就可以解決以上問題，刪除倒數第 n 個節(jié)點后，返回的 preHead.next 即可
  • 另外一種是，fast 快指針提前走 n 步后，判斷 fast.next 是否為 null ，即 fast 是否是最后一個節(jié)點，如果是，則 head 為倒數第 n 個節(jié)點，此時問題可以簡化為刪除頭節(jié)點;如果不是， fast = fast.next ，fast 再前進一步，slow 為倒數第 n+1 個節(jié)點，也解決了以上問題。

解決方案一：添加 preHead 節(jié)點

 
 
 
    
  
  
  
  1. const removeNthFromEnd = function(head, n) { 
    2. 
  
  
  
  2.     let preHead = new ListNode(0) 
    3. 
  
  
  
  3.     preHead.next = head 
    4. 
  
  
  
  4.     let fast = preHead, slow = preHead 
    5. 
  
  
  
  5.     // 快先走 n+1 步 
    6. 
  
  
  
  6.     while(n--) { 
    7. 
  
  
  
  7.         fast = fast.next 
    8. 
  
  
  
  8.     } 
    9. 
  
  
  
  9.     // fast、slow 一起前進 
    10. 
  
  
  
  10.     while(fast && fast.next) { 
    11. 
  
  
  
  11.         fast = fast.next 
    12. 
  
  
  
  12.         slow = slow.next 
    13. 
  
  
  
  13.     } 
    14. 
  
  
  
  14.     slow.next = slow.next.next 
    15. 
  
  
  
  15.     return preHead.next 
    16. 
  
  
  
  16. }; 
    17.

解決方案二：單獨處理倒數第 n 節(jié)點

 
 
 
    
  
  
  
  1. const removeNthFromEnd = function(head, n) { 
    2. 
  
  
  
  2.     let fast = head, slow = head 
    3. 
  
  
  
  3.     // 快先走 n 步 
    4. 
  
  
  
  4.     while(--n) { 
    5. 
  
  
  
  5.         fast = fast.next 
    6. 
  
  
  
  6.     } 
    7. 
  
  
  
  7.     if(!fast.next) return head.next 
    8. 
  
  
  
  8.     fast = fast.next 
    9. 
  
  
  
  9.     // fast、slow 一起前進 
    10. 
  
  
  
  10.     while(fast && fast.next) { 
    11. 
  
  
  
  11.         fast = fast.next 
    12. 
  
  
  
  12.         slow = slow.next 
    13. 
  
  
  
  13.     } 
    14. 
  
  
  
  14.     slow.next = slow.next.next 
    15. 
  
  
  
  15.     return head 
    16. 
  
  
  
  16. }; 
    17.

時間復雜度：O(n)

空間復雜度：O(1)

來源：https://github.com/sisterAn/JavaScript-Algorithms


當前文章：每日：刪除鏈表倒數第N個結點
URL標題：http://www.5511xx.com/article/ccoeggg.html