JavaScript——链表相关

反转链表

输入一个链表，反转链表后，输出新链表的表头。

例如：

输入：a->b->c->d->e

输出：a<-b<-c<-d<-e

反转链表示意图如下，链表的最后一个元素 next 指向 null。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function isEmptyObject(obj) {// 判断输入参数链表是否为空
  for (var name in obj) {
      return false;
  }
  return true;
}

function ReverseList(pHead) {
    if (isEmptyObject(pHead)) {// 调用链表是否为空函数
        return false;
    }
    var pre = null;//链表的最后一个元素
    var next = null;//初始化next为null，下面再赋值
    while (pHead != null) {//pHead移动，直至到链表最后一个元素，指向null，结束循环
        next = pHead.next;//pHead.next值先赋给next，以免覆盖，next移动
        pHead.next = pre;//改变pHead指向，给pHead.next赋值，指向null
        pre = pHead;//pre移动
        pHead = next;//pHead移动
    }
    return pre;
}

单链表是否有环

1. 创建哈希表,不过会占⽤较⼤的空间,不是最佳⽅法.( 时间复杂度 O(n) )

function judge(list){
  var set =new Set();
  while(list){
    if(set.has(list)){
      return true
    }
    set.add(list)
    list=list.next()
  }
}

2. 给节点添加 visited 访问标记 (时间复杂度 O(n)), 不需要额外的空间

function LinkedList(){
  var Node=function(){
    this.element=element;
    this.next=null;
    this.visited=0; //访问标记
  }
}

function judge(list){
  while(list){
    if(list.visited==1){
     return true
    }
    list.visited=1
    list=list.next()
  }
}

3. 快慢指针法,设定快指针 fast,慢指针 slow,每次循环快指针 fast 移动两个位置,慢指针移动⼀个位置
   (时间复杂度 O(n)) 需要额外的空间

function judge(list){
  var fast=list.next.next,
  slow=list.next;
  while(fast){
    if(fast===slow){
          return true
    }
    fast=fast.next.next
    slow=slow.next
  }
}