JAVASCRIPT算法（3）

Yi_Zhi_Yu 發(fā)布于2019-08-21 17:52 / 3456人閱讀

摘要：首先是鏈表的定義語法搞錯(cuò)了。分析本題與編程之美上的從無頭單鏈表中刪除節(jié)點(diǎn)類似。但是如果節(jié)點(diǎn)是尾節(jié)點(diǎn)時(shí)，該方法就行不通了。分析非遞歸的算法很簡(jiǎn)單，用三個(gè)臨時(shí)指針在鏈表上循環(huán)一遍即可。遞歸算法是先逆轉(zhuǎn)下一個(gè)節(jié)點(diǎn)，再逆轉(zhuǎn)當(dāng)前節(jié)點(diǎn)。

鏈接描述## 面試前準(zhǔn)備了Promise的一種實(shí)現(xiàn)（大致理解和寫出來），二叉樹的構(gòu)建，刪除，查找，插入，快排的非遞歸，準(zhǔn)備了蠻多的吧，但是沒考慮鏈表。然后考個(gè)鏈表的反轉(zhuǎn)，其實(shí)很簡(jiǎn)單，只不過有點(diǎn)懵，比我想的稍微難了點(diǎn)，然后這種考慮算法的實(shí)現(xiàn)而忽略了特殊情況的考慮，雖然我確定我能寫出來，但是在那段懵的時(shí)間沒有。后來看到了我朋友寫的鏈表面試題，鏈接在此。

我朋友是做Android開發(fā)的，以java的形式舉了幾個(gè)例子。我是眼高手低，還是練練javascript的形式吧。

首先是鏈表的定義
/*class Node{ //語法搞錯(cuò)了。
constructor(val){
this.val= val;
this.next = null;
}
}*/
function Node(val){
this.val = val;
this.next = null;
}

題目描述：給定單鏈表中需要?jiǎng)h除的節(jié)點(diǎn)（不是尾節(jié)點(diǎn)），在 O(1) 時(shí)間刪除該節(jié)點(diǎn)。

分析：本題與《編程之美》上的「從無頭單鏈表中刪除節(jié)點(diǎn)」類似。主要思想都是「貍貓換太子」，即用下一個(gè)節(jié)點(diǎn)數(shù)據(jù)覆蓋要?jiǎng)h除的節(jié)點(diǎn)，然后刪除下一個(gè)節(jié)點(diǎn)。但是如果節(jié)點(diǎn)是尾節(jié)點(diǎn)時(shí)，該方法就行不通了。

function deleteNode(node){
 if(node==null||node.next==null) return ;
 node.val = node.next.val;
 node.next = node.next.next;
}

題目描述：輸出一個(gè)單鏈表的逆序反轉(zhuǎn)后的鏈表。

分析：非遞歸的算法很簡(jiǎn)單，用三個(gè)臨時(shí)指針 prev、cur、next 在鏈表上循環(huán)一遍即可。遞歸算法是先逆轉(zhuǎn)下一個(gè)節(jié)點(diǎn)，再逆轉(zhuǎn)當(dāng)前節(jié)點(diǎn)。

有點(diǎn)傷心的題目啊，其實(shí)還是蠻簡(jiǎn)單的，就是在改變next的指向的時(shí)候，保留next指向的節(jié)點(diǎn)。

function reverseByLoop(head){
     if(head == null || head.next == null) return head;
     var pre = null,
         next;
     while(head!=null){
       next = head.next;
       head.next = pre;
       pre = head;
       head = next;
     }
     return pre;
}

function reverseByRecursion(head){
  if(head==null||head.next ==null) return head;
  //遞歸的好難理解。。
  var headOfNext = reverseByRecursion(head.next);
  head.next.next = head;
  head.next = null;
  return headOfNext;
  
}

遞歸有一種給我一個(gè)支點(diǎn)和足夠長(zhǎng)的棍，我就能翹起地球一樣的感覺。
比如原鏈表是這樣的結(jié)構(gòu)A->B->C->D->E.
既然這個(gè)function的目的是把鏈表倒序，那么如果我調(diào)用reverseByRecursion(B),
那么返回的結(jié)果一定是E,并且E->D->C->B.
現(xiàn)在我手中還有A，A->B。所以為了形成E->D->C->B->A, 只需要把B指向A,然后A指向NULL. 所以就是后續(xù)操作了。

那么還需要驗(yàn)證臨界情況，即最里面一層執(zhí)行的狀態(tài)能否達(dá)成逆轉(zhuǎn)鏈表的效果。
調(diào)用棧如下
reverseByRecursion(E)->return E;
reverseByRecursion(D)-> D.next.next=D;=>E->D D.next=NULL; return E; E->D->NULL
reverseByRecursion(C)-> C.next.next=C;=>D.next=C C.next=NULL; return E;=>E->D->C->NULL
reverseByRecursion(B)
reverseByRecursion(A)

先這樣吧。果然有點(diǎn)眼高手低。