投稿015期 | 数据结构与算法

这些都是数据结构与算法，一部分方法是团队其他成员实现的，一部分我自己做的，有什么其他实现方法或错误，欢迎各位大佬指点，感谢。

解析：
概念参考阅读 链表 —— 维基百科

1.概念：

链表（linked list）是一种上一个元素的引用指向下一个元素的存储结构，链表通过指针来连接元素与元素；

链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。

2.与数组的区别：

• 相同：
  两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

• 不同：
  链表是链式的存储结构；数组是顺序的存储结构。
  链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。

链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难。

数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。

数组和链表一些操作的时间复杂度对比：
数组：

• 查找复杂度：O(1)
• 添加/删除复杂度：O(n)

链表：

• 查找复杂度：O(n)
• 添加/删除复杂度：O(1)

3.生活中的案例：
火车，是由一些列车厢连接起来；
寻宝游戏，每个线索都是下一个线索地点的指针。

• append(element)：向列表尾部添加一个新的元素。
• insert(position, element)：向列表指定位置插入一个新的元素。
• remove(element)：从列表中移除并返回特定元素（若有多个相同元素则取第一次出现的情况）。
• indexOf(element)：返回元素在列表的索引（若有多个相同元素则取第一次出现的情况），如果列表中没有该元素则返回 -1。
• removeAt(position)：从列表中，移除并返回特定位置的一项。
• isEmpty()：如果列表不含任何元素，返回 true，否则返回 false。
• size()：返回列表中元素个数，与数组的 length 属性类似。
• toString()：由于列表项使用 Node 类，需要重写继承自 Javascript 对象默认的 toString() 方法，让其只输出元素的值。
  提示：Web 端优先使用 ES6 以上的语法实现。

解析：

class Node {
    constructor(element){
 this.element = element
 this.next = null
    }
}
class linkedList {
    constructor(){
 this.length = 0
 this.head = null
    }
    
    append(element){
 let node = new Node(element)
 if(!this.head){
     this.head = node
 }else{
     let current = this.head
     // 查找最后一项
     while(current.next){
  current = current.next
     }
     // 将最后一下的next赋值为node，实现追加元素
     current.next = node
 }
 this.length ++
    }
    
    insert(position, element){
 if(position >= 0 && position <= this.length){
     let node = new Node(element),
  index = 0,
  previous = null
     if(position === 0){
  node.next = this.head
  this.head = node
     }else{
  let current = this.head
  while(index++ < position){
      previous = current
      current = current.next
  }
  previous.next = node
  node.next = current
     }
     this.length ++
 }
    }
    
    remove(element){
 let current = this.head,
     previous = null
 if(element === this.head.element){
     this.head = current.next
 }else{
     while(current.next && current.element !== element){
  previous = current
  current = current.next
     }
     previous.next = current.next
     this.length --
     return current.element
 }
    }
    
    removeAt(position){
 if(position >= 0 && position <= this.length){
     let current = this.head,
  index = 0,
  previous = null
     if(position === 0){ // 删除第一项
  this.head = current.next
     }else{
  while(index++ < position){
      previous = current
      current = current.next
  }
  previous.next = current.next
     }
     this.length --
     return current.element
 }
    }
    
    indexOf(element){
 let current = this.head, 
     index = 0
 while(current.next && current.element !== element){
     current = current.next
     index ++
 }
 return index === 0 ? -1 : index
    }
    
    isEmpty(){
 return this.length === 0
    }
    
    size(){
 return this.length
    }
    
    toString(){
 let current = this.head,
     arr = new Array()
 while(current.next){
     arr.push(current.element)
     current = current.next
 }
 arr.push(current.element)
 return arr.toString()
    }
}

let leo = new linkedList()
leo.append(3)
leo.append(6)
leo.append(9)
console.log(leo.length)
console.log(leo.head)
leo.remove(6)
console.log(leo.length)
console.log(leo.head)
console.log(leo.toString())

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
// input
let head = {
    'val': 1,'next': {
 'val': 2,'next': {
     'val': 3,'next': {
  'val': 4,'next': {
      'val': 5,
      'next': null
  }
     }
 }
    }
};
reverseList(head)

// output
head = {
    'val': 5,'next': {
 'val': 4,'next': {
     'val': 3,'next': {
  'val': 2,'next': {
      'val': 1,
      'next': null
  }
     }
 }
    }
};

let reverseList = function(head) {
    let pre = null, curr = head
    while (curr) {
 next = curr.next
 curr.next = pre
 pre = curr
 curr = next
    }
    return pre
};

let reverseList = function(head) {
    if(head == null || head.next == null) return head
    let pre = reverseList(head.next)
    head.next.next = head
    head.next = null
    return pre
};

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

let hasCycle = function(head) {
    while(head){
 if(head.value == null) return true
 head.value = null
 head = head.next
    }
    return false
}

let hasCycle = function(head) {
    let node = head
    while(node){
 if(node.isVisit){
     return true
 }else{
     node.isVisit = true
 }
 node = node.next
    }
    return false
};

let hasCycle = function(head) {
    if(head == null || head.next == null) return false
    let slow = head, fast = head.next
    while(slow != fast){
 if(fast == null || fast.next == null) return false
 slow = slow.next  // 慢指针每次走1步
 fast = fast.next.next // 快指针每次走1补
    }
    return true
};

给定 1->2->3->4, 你应该返回 2->1->4->3.
给定 1->2->3->4->5, 你应该返回 2->1->4->3->5.

let swapPairs = function (head){
    if(!head) return null
    let arr = []
    while(head){
 let next = head.next
 head.next = null
 arr.push(head)
 head = next
    }

    for(let i = 0; i < arr.length; i += 2){
 let [a, b] = [arr[i], arr[i + 1]]
 if(!b) continue
 [arr[i], arr[i + 1]] = [b, a]
    }

    for(let i = 0; i < arr.length - 1; i ++){
 arr[i].next = arr[i + 1]
    }
    return arr[0]
}

let swapPairs = function (head){
    if(head == null || head.next ==null) return head
    let next = head.next
    head.next = swapPairs(next.next)
    next.next = head
    return next
}