JAVASCRIPT算法(3)


链接描述## 面试前准备了Promise的一种实现(大致理解和写出来),二叉树的构建,删除,查找,插入,快排的非递归,准备了蛮多的吧,但是没考虑链表。然后考个链表的反转,其实很简单,只不过有点懵,比我想的稍微难了点,然后这种考虑算法的实现而忽略了特殊情况的考虑,虽然我确定我能写出来,但是在那段懵的时间没有。后来看到了我朋友写的链表面试题,链接在此。

我朋友是做Android开发的,以java的形式举了几个例子。我是眼高手低,还是练练javascript的形式吧。


首先是链表的定义
class Node(){
constructor(val){
this.val= val;
this.next = null;
}
}


题目描述:给定单链表中需要删除的节点(不是尾节点),在 O(1) 时间删除该节点。

分析:本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」,即用下一个节点数据覆盖要删除的节点,然后删除下一个节点。但是如果节点是尾节点时,该方法就行不通了。


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

题目描述:输出一个单链表的逆序反转后的链表。

分析:非递归的算法很简单,用三个临时指针 prev、cur、next 在链表上循环一遍即可。递归算法是先逆转下一个节点,再逆转当前节点。

有点伤心的题目啊,其实还是蛮简单的,就是在改变next的指向的时候,保留next指向的节点。

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;
  
}

递归有一种给我一个支点和足够长的棍,我就能翘起地球一样的感觉。
比如原链表是这样的结构A->B->C->D->E.
既然这个function的目的是把链表倒序,那么如果我调用reverseByRecursion(B),
那么返回的结果一定是E,并且E->D->C->B.
现在我手中还有A,A->B。所以为了形成E->D->C->B->A, 只需要把B指向A,然后A指向NULL. 所以就是后续操作了。

那么还需要验证临界情况,即最里面一层执行的状态能否达成逆转链表的效果。
调用栈如下
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)


先这样吧。果然有点眼高手低。


发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>