前端学数据结构:链表

126 阅读3分钟

本文首发于我的Github

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和指向下一个元素的 引用 组成。

------------------------------------------------------------------------
|                                                                      |
|                node                      node               null     |
|           ---------------          ---------------        --------   |
|  head ->  + item | next +    ->    + item | next +   ->   + null +   |
|           ---------------          ---------------        --------   |
|                                                                      |
------------------------------------------------------------------------
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  /**
   * 添加节点
   * @param {*} value
   */
  append(value) {
    return this.insert(value, this.length);
  }

  /**
   * 添加节点到指定位置
   * @param {*} value
   * @param {*} position
   */
  insert(value, position) {
    if (position < 0 || position > this.length) {
      return false;
    }

    let node = new Node(value);

    if (position === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let prev = null;
      let current = this.head;
      let i = 0;

      while (i++ < position) {
        prev = current;
        current = current.next;
      }

      prev.next = node;
      node.next = current;
    }

    this.length++;
    return true;
  }

  /**
   * 移出指定位置的节点
   * @param {*} position
   */
  removeAt(position) {
    if (position < 0 || position > this.length) {
      return false;
    }

    if (position === 0) {
      this.head = this.head.next;
    } else {
      let prev = null;
      let current = this.head;
      let i = 0;

      while (i++ < position) {
        prev = current;
        current = current.next;
      }

      prev.next = current.next;
    }

    this.length--;
    return true;
  }

  /**
   * 查找给定值所在索引
   * @param {*} value
   */
  indexOf(value) {
    let current = this.head;
    let index = -1;

    while (current) {
      indeex++;
      if (current.value === value) {
        return index;
      } else {
        current = current.next;
      }
    }

    return -1;
  }

  reverse() {
    let prev = null;
    let current = this.head;
    let next = null;

    while (current) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    this.head = prev;
  }

  traverseFromTailToHead() {
    let stack = [];
    let current = this.head;

    while (current) {
      stack.push(current);
      current = current.next;
    }

    while (stack.length) {
      stack.pop();
    }
  }

  getKthNodeFromTailToHead(k) {
    let p1 = this.head;
    let p2 = this.head;
    let i = 0;

    while (i++ < k) {
      p1 = p1.next;
    }

    while (p1) {
      p1 = p1.next;
      p2 = p2.next;
    }

    return p2;
  }
}

题目

1. 输出单链表倒数第 k 个节点

问题描述

题目:输入一个单链表,输出此链表中的倒数第 K 个节点。(去除头结点,节点计数从 1 开始)。

解题思路

倒数第 k 个节点即为整数第 n - k 个节点(n 为链表长度)

  • 定义 2 个指针同时执行链表头节点
  • 第 1 个指针前进 k 个 节点
  • 两个指针同时前进,当第 1 个指针到达链表尾时,第 2 个指针与第一个指针相距 k 个节点,第二个指指向节点即为所求
function findKthTail(linkList, k) {
  let p1 = linkList.head;
  let p2 = linkList.head;
  let i = 0;

  while (i++ < k) {
    p1 = p1.next;
  }

  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p2; 
}

2. 判断链表是否有环

问题描述

单链表中的环是指链表末尾的节点的 next 指针不为 NULL ,而是指向了链表中的某个节点,导致链表中出现了环形结构。

0 -> 1 -> 2 -> 3 -> 4
               |    |
               6 <- 5

链表中尾节点 6 指向了 节点 3 而非 null,导致出现了环形结构。

解题思路

  • 定义 2 个快慢指针,初始均指向头节点
  • 第 1 个指针前进 1 步,第 2 个指针前进 2 步
  • 若是无环,2 个指针最后均指向 null,但若是有环,2 指针必定在一个节点处相遇,该节点不为 null
/**
 * 判断链表是否存在环
 * @param {*} linkList
 */
function isExistLoop(linkList) {
  let p1 = linkList.head;
  let p2 = linkList.head;

  while (p1 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 === p2) {
      return true;
    }
  }

  return false;
}

问题描述

定位环的起点。

解题思路

定义2个快慢指针,第一次先找到 2 个指针在环中的相遇点,然后令 p1 指向 相遇点,p2 指向头节点,同时出发(每次走过的节点相同),当 2 指针指向的节点相同时,p1 即为环的起点。

function getMeetingNode(linkList) {
  let p1 = linkList.head;
  let p2 = linkList.head;

  while (p1 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 == p2) {
      return p1;
    }
  }

  return null;
}

function getEntryOfLoop(linkList) {
  let meetingNode = linkList.getMeetingNode();

  if (!meetingNode) {
    return null;
  }

  let p1 = meetingNode;
  let p2 = linkList.head;

  while (p1 != p2) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}