huskyAreYouScared-Blog

# 链表

# 用JS实现链表

  • 先写一下链表所需要的属性和方法
function LinkedList(){
  this.head = null // 链表的首位
  this.length = 0 // 链表的长度
  // 链表节点
  function Node(value){
    this.value = value
    this.next = null
  }
  this.append = function (){} // 向尾部添加新的节点
  this.insert(position,element) // 向链表特定位置插入元素；
  this.remove(element) // 从链表移除一项；
  this.indexOf(element) // 返回链表中某元素的索引，如果没有返回-1；
  this.removeAt(position) // 从特定位置移除一项；
  this.isEmpty() // 判断链表是否为空，如果为空返回true,否则返回false;
  this.size() // 返回链表包含的元素个数；
  this.toString() // 重写继承自Object类的toString()方法，因为我们使用了Node类；
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 实现append

function LinkedList(){
  this.head = null // 链表的首位
  this.length = 0 // 链表的长度
  // 链表节点
  function Node(value){
    this.value = value
    this.next = null
  }
  // 向尾部添加新的节点
  this.append = function (value){
    let newNode = new Node(value)
    if(this.length === 0){
      this.head = newNode
    }else{
      let current = this.head
      while(current.next){
        current = current.next
      }
      current.next = newNode
    }
    this.length++
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 实现insert

// ... 省略 ...
this.insert = function (position,element){
  if(position>=0 && position<=this.length){
    let newNode = new Node(element)
    let current = this.head
    if(position === 0){
      newNode.next = current
      this.head = newNode
    } else {
      while(--position){
        current = current.next
      }
    }
    newNode.next = current.next
    current.next = newNode
    this.length++
    return true
  }else{
    return false
  }
}
// ... 省略 ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 实现indexOf

// ... 省略 ...
this.indexOf = function(element){
    let currnet = this.head
    let index = 0
    while(currnet){
      if(element === currnet.value){
        return index
      }
      currnet = currnet.next
      index++
    }
    return -1
  }
// ... 省略 ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 实现removeAt

// ... 省略 ...
this.removeAt = function(position){
    let current = this.head
    if(position>=0 && position<=this.length){
      let returnValue = null
      if(position === 0){
        returnValue = current
        this.head = current.next
      } else{
        let previous = null
        while(position--){
          previous = current
          current = current.next
        }
        returnValue = current
        previous.next = current.next
      }
      this.length--
      return returnValue
    }else{
      return false
    }
  }
// ... 省略 ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 实现remove

// ... 省略 ...
  this.remove = function(element){
    let postion = this.indexOf(element)
    return this.removeAt(postion)
  }
// ... 省略 ...
1
2
3
4
5
6

# 实现 isEmpty

  • 如果是空返回true，否则false
// ... 省略 ...
  this.isEmpty = function(){
    return this.length === 0
  }
// ... 省略 ...
1
2
3
4
5

# 实现 size

// ... 省略 ...
  this.size = function(){
    return this.length
  }
// ... 省略 ...
1
2
3
4
5

# 实现 toString

// ... 省略 ...
  this.toString = function() {
    let current = this.head
    let str = ''
    while(current){
      str +=current.value+(current.next?',':'')
      current = current.next
    }
    return str
  }
// ... 省略 ...
1
2
3
4
5
6
7
8
9
10
11

# 测试

let list = new LinkedList()
list.append(1)
list.append(3)

list.insert(0,4)
list.insert(0,4)

list.removeAt(1)
list.remove(3)

console.log(list.size()); // 2
console.log(list.head.next) // Node { value: 1, next: null }
console.log(list.toString()) // 4,1
1
2
3
4
5
6
7
8
9
10
11
12
13

# 双向链表

  • 所谓双向链表，其实就是在数据节点上增加前一个保留前一个节点的属性
  • 接下来实现一下和单链表一样的功能

# 基础结构

function LinkedList(){
  this.head = null
  this.length = 0

  function Node(value){
    this.value = value
    this.next = null
    this.prev = null //  和单链表区别的地方
  }
}
1
2
3
4
5
6
7
8
9
10

# 双向链表 append

// 向尾部添加新的节点
  this.append = function (value){
    let newNode = new Node(value)
    if(this.length === 0){
      this.head = newNode
    }else{
      let current = this.head
      while(current.next){
        current = current.next
      }
      newNode.prev = current
      current.next = newNode
    }
    this.length++
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 双向链表 insert

  // 向链表特定位置插入元素；
  this.insert=function(position, element) {
    let newNode = new Node(element)
    let current = this.head
    // 当还没有数据的时候
    if(position === 0 && this.length===0) {
      this.head = newNode
      return this.length++
    }
    // 当有数据插入到首个元素的时候
    if(position === 0 && this.length!==0){
      newNode.next = current
      current.prev = newNode
      this.head = newNode
      return this.length++
    } 
    // 多个元素的时候，插入到中间位置，如果索引大于当前的链表长度，插入失败返回false
    if (position > 0 && position <= this.length) {
      while(position>0 && current.next){
        current = current.next
        position--
      }
      if(current.next !== null){
        newNode.prev = current
        newNode.next = current.next
        current.next.prev = newNode
        current.next = newNode
      } else {
        newNode.prev = current
        newNode.next = null
        current.next = newNode
      }
      return this.length++
    }else {
      return false
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 双向链表 indexOf

  • 这个方法和但链表的一致
// 返回链表中某元素的索引，如果没有返回-1；
  this.indexOf=function(element) {
    let current = this.head
    let index = 0
    while(current){
      if(current.value === element){
        return index
      }
      current = current.next
      index++
    }
    return -1
  }
1
2
3
4
5
6
7
8
9
10
11
12
13

# 双向链表 removeAt

// 从特定位置移除一项；
  this.removeAt=function(position) {
    let current = this.head
    if(position>=0&&position < this.length){
      if(position === 0){
        this.head = current.next
        this.head.prev = null
      } else {

        let prev = null
        while(position--){
          prev = current
          current = current.next
        }

        prev.next = current.next

        if(current.next&&current.next.prev){ // 如果current.next是null则不做处理
          current.next.prev = prev
        }
      }     
      this.length--
      return true
    } else {
      return false
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 双向链表 remove

  • 该方法也和单链表一致，需要调用自身的indexOf和removeAt来实现
 // 从链表移除一项；
  this.remove=function(element) {
    let index = this.indexOf(element)
    if(index !== -1){
      this.removeAt(index)
      return true
    }
    return false
  }
1
2
3
4
5
6
7
8
9

# isEmpty 和 size 和 toString 和单链表一样

# 环形链表 即 最后一个元素的 next 指向 head

# 链表常见算法题

# 反转链表

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverse(head){
  let newHead = null
  while(head){
    let temp = head
    head = head.next
    temp.next = newHead
    newHead = temp
  }
  return newHead
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 俩俩交换链表数据

TIP

1->2->3->4 swapPairs 2->1->4->3

  • 解决方案一 循环迭代的方式
function swapPairs(head){
  let dummy = head.next
  let prev = null
  while(head && head.next){
    
    let firstNode = head
    let secondNode = head.next
    // 和上一轮的最后一位关联
    prev?prev.next = secondNode:''

    // swap
    firstNode.next = secondNode.next
    secondNode.next = firstNode
    
    // 准备下一轮赋值
    head = firstNode.next
    prev = firstNode
  }
  return dummy
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • 解决方案二 递归的方式
function swapPairs(head) {
  if(!head || !head.next) return head

  let firstNode = head
  let secondNode = head.next

  firstNode.next =  swapPairs(secondNode.next)
  secondNode.next = firstNode

  return secondNode
}
1
2
3
4
5
6
7
8
9
10
11

# 检测链表中是否有环

  • 如果有环输出该环的head，如果没有则返回null
  • 主要利用了快满指针的思想
var detectCycle = function(head) {
    let fast = head,slow = head;
    // 边界值判断
    if(!head||!head.next){
        return null
    }
    // 快慢指针循环，如果有相等的情况则代表有环
    while(fast&&fast.next){
        slow = slow.next
        fast = fast.next.next
        if(slow == fast){
            break
        }
    }
    // 上面的循环结束后，如果fast和slow不想等则代表没有环
    if(fast!= slow){
        return null
    }
    // 将slow指向链表最开始的位置
    slow = head
    // 接下来fast和slow每次循环走一步，直到相等后，就找到了有环链表的head
    while(fast!=slow){
        fast= fast.next
        slow = slow.next
    }
    return slow
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Last Updated: 1/23/2022, 10:16:22 AM

← 栈 →