JS中的链表(含leetcode例题)＜持续更新~＞

链表

特性

• 链表不同于数组，在内存中不必是连续的空间
• 链表中的每个元素由存储元素本身的节点和指向下一个元素的引用（指针）组成
• 链表在插入和删除时，时间复杂度为O(1)

其实前端中基本不太常用链表，所以还是主要学习一下编程思想

实现方式

// 封装链表类
function LinkedList(){
    
  // 内部类
  function Node(data){
    
    this.data = data
    this.next = null
  }

  // 属性
  this.head = null
  // 链表不像数组，可以直接获取长度，所以提前加入属性中
  this.length = 0

  // 1.append尾部追加
  LinkedList.prototype.append = function(data){
    
    // 创建新节点
    var newNode = new Node(data)
    // 添加的是第一个节点
    if(this.length == 0){
    
      this.head = newNode
    }else{
    
      // 添加的不是第一个节点
      // 先给current指向头，之后判断是否有下一个节点，有就转为下一个
      // 这样最终current就指向了最后一个节点
      var current = this.head
      while(current.next){
    
        current = current.next
      }
      current.next = newNode
    }
    this.length += 1
  }

  // 2.toString方法
  LinkedList.prototype.toString = function(){
    
    // 定义变量
    var current = this.head
    var listString = ""
    // 循环遍历
    while(current){
    
      listString += current.data
      current = current.next
    }
    return listString
  }

  // 3.insert插入
  LinkedList.prototype.insert = function(position,data){
    
    // 先对传入的position合法性进行校验
    if(position<0 || position>this.length) return false
    var newNode = new Node(data)
    // 情况一：插入的位置是第一个节点
    if(position == 0){
    
      // 插入节点指向head指向的节点
      newNode.next = this.head
      // head再指向插入的节点
      this.head = newNode
    }else{
    
      // 情况二：插入的位置不是第一个节点
      // 找到要插入的节点位置
      var index = 0
      // current用来找对应位置，previous找对应位置的前一个位置
      var current = this.head
      var previous = null
      while(index++ < position){
    
        previous = current
        current = current.next
      }
      newNode.next = current
      previous.next = newNode
    }
    this.length++

  }

  // 4.get方法
  LinkedList.prototype.get = function(position){
    
    // position合法性判断
    if(position<0 || position>=this.length) return null
    var current = this.head
    var index = 0
    while(index++ < position){
    
      current = current.next
    }
    return current.data
  }

    // 5.indexOf根据元素返回索引
    LinkedList.prototype.indexOf = function(data){
    
      var current = this.head
      var index = 0
      while(current){
    
        if(current.data == data){
    
          return index
        }
        current = current.next
        index += 1
      }
      return -1
    }

    // 6.update对应位置的data数据
    LinkedList.prototype.update = function(position,newData){
    
      // 边界判断
      if(position<0 || position>= this.length) return false
      var current = this.head
      var index = 0
      while(index++ < position){
    
        current = current.next
      }
      current.data = newData
      return true
    }

    // 7.removeAt从列表特定位置移除一项
    LinkedList.prototype.removeAt = function(position){
    
      if(position<0 || position >= this.length) return false
      if(position == 0){
    
        this.head = this.head.next
      }else{
    
        var index = 0
        var current = this.head
        var previous = null
        while(index++ < position){
    
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length -= 1
    }

    // 8.remove直接删除一项
    LinkedList.prototype.remove = function(data){
    
      // 获取位置
      var position = this.indexOf(data)
      // 根据位置删除
      return this.removeAt(position)
    }

    // 9.isEmpty判空
    LinkedList.prototype.isEmpty = function(){
    
      return this.length == 0
    }

    // 10.size()方法
    LinkedList.prototype.size = function(){
    
      return this.length
    }
    
}

leetcode例题

141. 环形链表

遍历链表，没有遍历过就存入map，遍历过说明成环，返回true

var hasCycle = function(head) {
    
    let map = new Map()
    while(head){
    
        if(map.get(head)) return true
        map.set(head,1)
        head = head.next
    }
    return false
};

21. 合并两个有序链表

// 递归实现
var mergeTwoLists = function(list1, list2) {
    
    if(list1 === null){
    
        return list2;
    }
    if(list2 === null){
    
        return list1;
    }
    if(list1.val < list2.val){
    
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }else{
    
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};

203. 移除链表元素

 // 本质是如何遍历链表
var removeElements = function(head, val) {
    
    // 创建虚拟头节点
    let Node = new ListNode(0)
    // 虚拟头节点的下一个是真正头节点
    Node.next = head
    let previous = Node
    while(previous.next){
    
        if(previous.next.val == val){
    
            previous.next = previous.next.next
        }else{
    
            previous = previous.next
        }
    }
    return Node.next
};

141. 环形链表

var hasCycle = function(head) {
    
    let map = new Map()
    while(head){
    
        if(map.get(head)) return true
        map.set(head,1)
        head = head.next
    }
    return false
};

21. 合并两个有序链表

var mergeTwoLists = function(list1, list2) {
    
    if(list1 === null){
    
        return list2;
    }
    if(list2 === null){
    
        return list1;
    }
    if(list1.val < list2.val){
    
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }else{
    
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};