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

RELATEED CONSULTING
相關(guān)咨詢(xún)
選擇下列產(chǎn)品馬上在線(xiàn)溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
每日：刪除鏈表倒數(shù)第N個(gè)結(jié)點(diǎn)

本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。

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

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

示例：

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

說(shuō)明：

給定的 n 保證是有效的。

進(jìn)階：

你能?chē)L試使用一趟掃描實(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í)問(wèn)題就變更為刪除鏈表中的 slow 的后繼節(jié)點(diǎn)

但存在一個(gè)問(wèn)題，當(dāng)鏈表長(zhǎng)度為 n 時(shí)，fast 是前進(jìn)不到 n+1 個(gè)節(jié)點(diǎn)位置的，所以此時(shí)有兩種解決思路：

  • 創(chuàng)建一個(gè)頭節(jié)點(diǎn) preHead ，設(shè)置 preHead.next = head ，這樣就可以解決以上問(wèn)題，刪除倒數(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í)問(wèn)題可以簡(jiǎn)化為刪除頭節(jié)點(diǎn);如果不是， fast = fast.next ，fast 再前進(jìn)一步，slow 為倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，也解決了以上問(wèn)題。

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

 
 
 
    
  
  
  
  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 一起前進(jìn) 
    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.

解決方案二：?jiǎn)为?dú)處理倒數(shù)第 n 節(jié)點(diǎn)

 
 
 
    
  
  
  
  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 一起前進(jìn) 
    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.

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

來(lái)源：https://github.com/sisterAn/JavaScript-Algorithms


當(dāng)前題目：每日：刪除鏈表倒數(shù)第N個(gè)結(jié)點(diǎn)
鏈接地址：http://m.5511xx.com/article/ccoeggg.html