数据结构：链表

发表于 | 分类于

链表

  • 用一组任意存储的单元来存储线性表的数据元素，一个对象存储着本身的值和下一个元素的地址
  • 需要遍历才能查询到元素，查询慢
  • 插入元素只需要断开连接重新赋值，插入快
1
2
3
4
function ListNode(x){
  this.val = x;
  this.next = null;
}

从尾到头打印链表

找当前节点的下一个节点从头部插入队列，直到null

1
2
3
4
5
6
7
8
function printFromTail(head){
  let array = [];
  while(head){
    array.unshift(head);
    head = head.next;
  }
  return array;
}

反转链表

思路：

  1. 定义三个变量prev、cur、next，表示上一个值，当前值，下一个值
  2. 如果存在cur.next，则将cur指向next
  3. 将cur移动到next位置，prev移动到cur位置，重复步骤2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function reverseList(head){
  let prev = null;
  let cur = head;
  if(head){
    let next = head.next;
    while(cur.next){
      cur.next = prev;
      prev = cur;
      cur = next;
      next = next.next;
    }
    cur.next = prev;
  }
  return cur;
}

反转部分链表

思路：

  1. 区间的反转同上
  2. m的next指向n的next，m前一位的next指向n
  3. 在第一位前加一位node，遍历到m。然后m到n再遍历，记录cur、prev这些
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    function reverseBetween(head, m, n) {
      let originList = new ListNode(0);
      originList.next = head;
      let headNode = originList;
      for(let i=0;i<m-1;i++) {
        headNode = headNode.next;
      }
      let prev = null;
      let cur = headNode.next;
      for(let i=0;i<n-m+1;i++) {
        let next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
      }
      headNode.next.next = cur;
      headNode.next = prev;
      return originList.next;
    }

删除链表中的节点

  • 传入函数的唯一参数为要被删除的节点 。
    思路： 改变node的val和next指向
1
2
3
4
function deleteNode(node) {
  node.val = node.next.val;
  node.next = node.next.next;
}

删除排序链表重复元素

思路：

  1. 使用cur、next两个指针表示当前值和下一个值
  2. 让cur指向head，开始遍历
  3. 若cur指针的值与next指针的值相等，则将next指针往后移动一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function deleteDuplicate(head) {
  if (!head) return head
  const listNode = new ListNode(0);
  listNode.next = head;
  let cur = listNode.next;
  while (cur) {
    let next = cur.next;
    while(cur) {
      // 重新定义next
      let next = cur.next;
      while(next && cur.val === next.val) {
        next = next.next;
      }
      cur.next = next;
      //继续往下一个
      cur = cur.next;
    }
    return listNode.next
  }
}

链表倒数第k个节点

思路：

  1. 设定两个节点，间距相差k个节点，当前面的节点到达终点，取后面的节点
  2. 当前面的节点到达k后，后面的节点才出发
  3. 考虑head为null，k为0，k大于链表长度的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function FindKthToTail(head, k) {
  if(!head || !k) return null;
  let front = head;
  let behind = head;
  let index = 1;
  while(front.next){
    index ++;
    front = front.next;
    if(k<index){
      behind = behind.next;
    }
  }
  if(index>=k) return behind;
  else return null;
}