数据结构与算法-链表

《学习JavaScript数据结构与算法(第3版)》

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

链表数据结构（单向链表）

链表的第一个节点为头部，链表最后一个节点的下一个元素始终是undefined或null。

// 比较链表中的元素是否相等
function defaultEquals(a, b) {
  return a === b;
}

// 节点类
class Node {
  constructor(element, next) {
    this.element = element; // 表示要加入链表元素的值
    this.next = next; // 指向链表中下一个元素的指针
  }
}

class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn;
    this.count = 0; // 存储链表中的元素数量
    this.head = undefined; // 保存引用
  }
  // 向链表尾部添加一个新元素
  push(element) {
    const node = new Node(element); // 创建节点类
    let current; // 插入位
    if (this.head == null) {
      // catches null && undefined
      this.head = node;
    } else {
      current = this.head; // 默认初始插入位为头部
      while (current.next != null) { // 一直找到链表的最后一项
        current = current.next;
      }
      // 将插入位的next赋为新元素，建立链接
      current.next = node;
    }
    this.count++; // 增加链表长度
  }
  // 返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined
  getElementAt(index) {
    // 检查越界值
    if (index >= 0 && index <= this.count) {
      // 从头开始循环
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }
  // 向链表的特定位置插入一个新元素
  insert(element, index) {
    // 检查越界值
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        // 在头部添加
        const current = this.head;
        // 将新插入的元素下一个节点指向原链表的head
        node.next = current;
        // 替换链表的head
        this.head = node;
      } else {
        // 查找到目标位的前一个元素
        const previous = this.getElementAt(index - 1);
        // 替换前一个元素的下一个引用 从而插入元素 形成链接
        node.next = previous.next;
        previous.next = node;
      }
      // 链表长度增加
      this.count++;
      return true;
    }
    // 越界了就无法添加到链表中
    return false;
  }
  // 从链表的特定位置移除一个元素
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head; // 默认移除点为头部
      if (index === 0) { // 移除第一项（头部）
        this.head = current.next;
      } else {
        // 查找到需要移除的位置前一项 解除链接关系
        const previous = this.getElementAt(index - 1);
        // 循环列表的当前元素引用 移除点
        current = previous.next;
        // 将previous与current的下一项链接起来：跳过current，从而实现移除
        previous.next = current.next;
      }
      // 链表长度减少
      this.count--;
      // 返回被移除项的值
      return current.element;
    }
    // 未有移除项
    return undefined;
  }
  // 从链表中移除一个元素 先找到索引值后根据索引值删除元素
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  // 能够在链表中找到一个特定的元素
  indexOf(element) {
    let current = this.head;
    // 为了运行不会发生错误，需要验证一下current的有效性
    for (let i = 0; i < this.size() && current != null; i++) {
      if (this.equalsFn(element, current.element)) {
        // 返回查找的索引值
        return i;
      }
      current = current.next;
    }
    // 没有找到返回-1
    return -1;
  }
  // 如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
  isEmpty() {
    return this.size() === 0;
  }
  // 返回链表包含的元素个数
  size() {
    return this.count;
  }
  // 返回链表第一个元素
  getHead() {
    return this.head;
  }
  // 清空链表
  clear() {
    this.head = undefined;
    this.count = 0;
  }
  // 返回表示整个链表的字符串。由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值
  toString() {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

双向链表提供了两种迭代的方法：从头到尾，或者从尾到头。可以根据位置确认从头遍历还是从尾部遍历。可以优化单向列表通过索引查找元素的方法。

// 比较链表中的元素是否相等
function defaultEquals(a, b) {
  return a === b;
}

// 双向链表节点
class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);
    this.prev = prev; // 指向上一个节点
  }
}

// 扩展普通链表类 继承LinkedList
class DoublyLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    this.tail = undefined; // 尾部 保存对链表的最后一个元素的引用 
  }
  push(element) {
    const node = new DoublyNode(element);
    if (this.head == null) {
      // 如果没有头部元素，则表示链表为空
      // 插入的节点为头部元素同时为尾部元素
      this.head = node;
      this.tail = node;
    } else {
      // 链表不为空，则从尾部插入元素
      this.tail.next = node; // 原尾部元素next指向待插入点
      node.prev = this.tail; // 待插入点prev指向原尾部元素
      this.tail = node; // 待插入点替换尾部元素
    }
    // 链表长度增加
    this.count++;
  }
  insert(element, index) {
    // 检查边界值
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;
      if (index === 0) {
        // 在链表头部插入元素
        if (this.head == null) {
          // 如果没有头部 则表示当前链表长度为0 头部元素和尾部元素都是待插入节点
          this.head = node;
          this.tail = node;
        } else {
          // 替换链表头部元素，且原头部元素上一个节点指向待插入节点
          node.next = this.head;
          this.head.prev = node;
          this.head = node;
        }
      } else if (index === this.count) {
        // 在链表尾部插入元素
        // 替换链表尾部元素，原尾部元素next指向为null/undefined，改为指向插入节点
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        // 查找到插入点的前一个元素
        const previous = this.getElementAt(index - 1);
        current = previous.next; // 待插入节点位置
        node.next = current; // 待插入节点next指向替换previous.next指向
        previous.next = node; // previous节点建立与待插入节点的链接
        current.prev = node; // current节点与待插入节点建立prev链接关系
        node.prev = previous; // 待插入节点prev指向previous节点，建立链接
      }
      // 链表长度增加
      this.count++;
      // 插入成功
      return true;
    }
    // 插入失败，超出边界值范围
    return false;
  }
  removeAt(index) {
    // 检查边界值
    if (index >= 0 && index < this.count) {
      // 待删除元素从头遍历
      let current = this.head;
      if (index === 0) {
        // 删除头部元素
        this.head = this.head.next;
        if (this.count === 1) {
          // 如果只有一项，需要删除尾部元素，新的head也为undefined
          this.tail = undefined;
        } else {
          // 需要更新head元素的prev引用
          this.head.prev = undefined;
        }
      } else if (index === this.count - 1) {
        // 最后一项
        current = this.tail;
        this.tail = current.prev; // 更新tail元素为尾部元素的prev
        this.tail.next = undefined; // 更新tail元素next指向
      } else {
        // 查找到待删除元素
        current = this.getElementAt(index);
        const previous = current.prev;
        // 将previous与current的下一项链接起来，删除current
        previous.next = current.next;
        current.next.prev = previous;
      }
      // 链表长度减少
      this.count--;
      // 返回删除元素值
      return current.element;
    }
    // 超出边界值
    return undefined;
  }
  // 查找值所在索引
  indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current != null) {
      if (this.equalsFn(element, current.element)) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }
  // 返回头部元素
  getHead() {
    return this.head;
  }
  // 返回尾部元素
  getTail() {
    return this.tail;
  }
  // 清除双向链表
  clear() {
    super.clear();
    this.tail = undefined;
  }
  // 返回表示整个链表的字符串
  toString() {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    while (current != null) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
  // 返回表示整个链表的反向字符串
  inverseToString() {
    if (this.tail == null) {
      return '';
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用undefined，而是指向第一个元素（head）。

下面的数据结构为单向引用的循环链表：

// 单向引用的循环链表，继承单向链表类
class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
  }
  // 向尾部添加新元素
  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      // 链表为空时，插入元素为head元素
      this.head = node;
    } else {
      // 链表的最后一个元素
      current = this.getElementAt(this.size() - 1);
      current.next = node; // 最后一个元素next指向新元素
    }
    // 设置最后一个节点next指向头部元素
    node.next = this.head;
    this.count++;
  }
  // 插入新元素
  insert(element, index) {
    // 检查边界值
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        // 插入位为头部head
        if (this.head == null) {
          // 空链表中插入元素则为head，head节点的next就需要指向自己
          this.head = node;
          node.next = this.head;
        } else {
          // 非空链表在头部插入元素
          node.next = current; // next指向原head元素
          current = this.getElementAt(this.size()); // 最后一个元素
          // 更新最后一个元素
          this.head = node;
          current.next = this.head;
        }
      } else {
        // 中间位置插入元素
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }
  // 从任意位置移除元素
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head; // 待删除元素
      if (index === 0) {
        if (this.size() === 1) {
          // 链表长度为1时，只需要修改head元素
          this.head = undefined;
        } else {
          // 链表长度大于1，移除head元素
          const removed = this.head;
          // 查找到最后一个元素
          current = this.getElementAt(this.size() - 1);
          this.head = this.head.next; // 更新head
          current.next = this.head; // 最后一个元素next指向新的head元素
          current = removed; // 移除的元素
        }
      } else {
        // 待删除位的前一个元素
        const previous = this.getElementAt(index - 1);
        current = previous.next; // 待删除元素
        previous.next = current.next;
      }
      this.count--;
      return current.element; // 返回删除元素的值
    }
    return undefined;
  }
}

有序链表

有序链表是指保持元素有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

// 用来比较元素
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

// 比较元素相等
function defaultEquals(a, b) {
  return a === b;
}

class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn);
    this.equalsFn = equalsFn;
    this.compareFn = compareFn;
  }
  // 从尾部插入元素 同插入元素
  push(element) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
  }
  // 插入元素，插入位置需要链表查找后确定，index值不使用
  insert(element, index = 0) {
    if (this.isEmpty()) {
      // 空链表，直接插入在index为0的位置
      return super.insert(element, 0);
    }
    // 查找待插入位置
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(element, pos); // 调用父级插入方法
  }
  // 获取插入元素的位置
  getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    // 从头遍历整个链表
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(element, current.element);
      if (comp === Compare.LESS_THAN) {
        // 当待插入元素的值小于循环元素的值时 返回当前循环元素的索引
        return i;
      }
      // 下一个待比较元素
      current = current.next;
    }
    return i; // 待插入位置的索引值
  }
}

扩展：StackLinkedList类

使用DoublyLinkedList(双向链表)创建栈数据结构。对于栈来说，需要向链表尾部添加元素，或者从链表尾部移除元素。DoublyLinkedList类有列表最后一个元素（tail）的引用，无须迭代整个链表的元素就能获取它。双向链表可以直接获取头尾的元素，减少过程消耗，它的时间复杂度和原始的Stack实现相同，为O(1)。

也可以对LinkedList类进行优化，保存一个指向尾部元素的引用，并使用这个优化版本来代替DoublyLinkedList。

export default class StackLinkedList {
  constructor() {
    // 使用双向链表进行存储数据
    this.items = new DoublyLinkedList();
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.removeAt(this.size() - 1);
    return result;
  }
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.getElementAt(this.size() - 1).element;
  }
  isEmpty() {
    return this.items.isEmpty();
  }
  size() {
    return this.items.size();
  }
  clear() {
    this.items.clear();
  }
  toString() {
    return this.items.toString();
  }
}

Leetcode算法题

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入两个链表的head，输出新链表的head

// ListNode
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

// 方法1 -- 递归，返回的是新链表
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

// 方法2 -- 迭代
var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1); // 哑节点
    
    let current = prehead // 初始化为哑节点，从头开始迭代
    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            current.next = l1
            l1 = l1.next // l1重新赋值进入下次循环
        } else {
            current.next = l2
            l2 = l2.next // l2重新赋值进入下次循环
        }
        current = current.next // current到下一个节点
    }
    // l1 === null || l2 === null 有一个链表最后的节点未进入新链表中
    current.next = l1 === null ? l2 : l1
    return prehead.next
}

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表，在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

使用归并排序

// 需要使用到上一个算法-合并两个有序链表
// 自顶向下排序  从中间二分成两个链表排序后进行合并
const toSortList = (head, tail) => {
    if (head === null) {
        return head;
    }
    if (head.next === tail) {
        head.next = null;
        return head;
    }
    // 快慢双指针法，奇数个节点找到重点，偶数个节点找到中心左边的节点
    let slow = head, fast = head;
    while (fast !== tail) {
        slow = slow.next;
        fast = fast.next;
        if (fast !== tail) {
            fast = fast.next;
        }
    }
    const mid = slow;
    return mergeTwoLists(toSortList(head, mid), toSortList(mid, tail));
}

var sortList = function(head) {
    return toSortList(head, null);
}

// 自底向上排序
var sortList = function(head) {
    if (head === null) {
        return head;
    }
    let length = 0;
    let node = head;
    while (node !== null) {
        length++;
        node = node.next;
    }
    const dummyHead = new ListNode(0, head);
    // subLength <<= 1 => subLength *= 2
    // 细分到两个节点后再合并
    for (let subLength = 1; subLength < length; subLength <<= 1) {
        let prev = dummyHead, curr = dummyHead.next;
        while (curr !== null) {
            let head1 = curr;
            for (let i = 1; i < subLength && curr.next !== null; i++) {
                curr = curr.next;
            }
            let head2 = curr.next;
            curr.next = null;
            curr = head2;
            for (let i = 1; i < subLength && curr != null && curr.next !== null; i++) {
                curr = curr.next;
            }
            let next = null;
            if (curr !== null) {
                next = curr.next;
                curr.next = null;
            }
            const merged = mergeTwoLists(head1, head2);
            prev.next = merged;
            while (prev.next !== null) {
                prev = prev.next;
            }
            curr = next;
        }
    }
    return dummyHead.next;
};

反转单向链表

function ReverseList(pHead) {
    // write code here
    if (pHead === null) {
        return null
    }
    let pre = null
    let cur = pHead
    let nex = pHead.next
    while (cur) {
        cur.next = pre // 当前节点的下一个节点改为前一个节点
        pre = cur // 记录前一个节点的值 循环到下一个节点的时候和next互换
        cur = nex // 进入下一轮循环
        // 判断是否是最后一个节点
        nex = nex != null ? nex.next : null
    }
    return pre
}

环路检测

重建二叉树

根据前序遍历和中序遍历的结果，重建二叉树。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

function reConstructBinaryTree(pre, vin) {
    // write code here
    // 前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，
    // 左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。
    // pre 前序遍历结果 根->左->右 vin 中序遍历结果 左->根->右
    if (pre.length === 0 || vin.length === 0) {
        return null
    }
    let val = pre[0] // 前序遍历 第一个节点为根节点
    // 建立根结点
    let node = new TreeNode(val)
    // 根节点所在的中序遍历的位置 则左边就是左子树 右边是右子树
    let index = vin.indexOf(val)
    // 左子树 前序遍历和中序遍历的左子树节点数相同 截断作为前序和中序遍历子数组 递归
    node.left = reConstructBinaryTree(pre.slice(1, index + 1), vin.slice(0, index))
    // 右子树 中序遍历vin要跳过index 前序遍历根节点为第一个元素
    node.right = reConstructBinaryTree(pre.slice(index + 1), vin.slice(index + 1))
    // 返回根节点
    return node
}

module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};