常见链表算法

[Leo-lin214]

对链表数据结构常见的算法进行总结，也为了更好滴应对后面深入学习算法。

从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个数组。

答案

  const returnReverseLink = head => {
    const result = [];
    while (head) {
      result.unshift(head.val);
      head = head.next;
    }
    return result;
  }
  

反转链表

输入一个链表，反转链表后，输出新链表的表头。

答案

  const reverseLink = head => {
    let currentNode = null;
    let headNode = head;
    while (head && head.next) {
      currentNode = head.next;
      head.next = currentNode.next;
      currentNode.next = headNode;
      headNode = currentNode;
    }
    return headNode;
  }
  

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后的复杂链表的head。

答案

  const copyComplexLink = head => {
    if (!head) return null;
    copyLink(head);
    copyRandomLink(head);
    return connectLink(head);
  }
  const copyLink = head => {
    let currentNode = head;
    while (currentNode) {
      const cloneNode = {
        val: currentNode.val,
        next: currentNode.next
      };
      currentNode.next = cloneNode;
      currentNode = cloneNode.next;
    }
  }
  const copyRandomLink = head => {
    let currentNode = head;
    while (currentNode) {
      const cloneNode = currentNode.next;
      const random = currentNode.random;
      if (random) {
        cloneNode.random = currentNode.random.next;
      } else {
        cloneNode.random = null;
      }
      currentNode = cloneNode.next;
    }
  }
  const connectLink = head => {
    const cloneHead = head.next;
    let cloneNode = head.next;
    let currentNode = head;
    while (currentNode) {
      if (cloneNode.next) {
        currentNode.next = cloneNode.next;
        cloneNode.next = cloneNode.next.next;
      } else {
        currentNode.next = null;
      }
      currentNode = currentNode.next;
      cloneNode = cloneNode.next;
    }
    return cloneHead;
  }
  

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

答案

  const concatLink = (aHead, bHead) => {
    if (!aHead) return bHead;
    if (!bHead) return aHead;
    let head;
    if (aHead.val > bHead.val) {
      head = bHead.val;
      head.next = concatLink(aHead, bHead.next);
    } else {
      head = aHead.val;
      head.next = concatLink(aHead.next, bHead);
    }
    return head;
  }
  

链表倒数第K个节点

输入一个链表，输出该链表中倒数第K个节点。

答案

  const getKNode = (head, k) => {
    if (!head || !k) return null;
    let front = head;
    let behind = head;
    let index = 1;
    while (front.next) {
      index++;
      front = front.next;
      if (index > k) {
        behind = behind.next;
      }
    }
    return index >= k ? behind : null;
  }
  

链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的入口节点，否则，输出null。

答案

  const getHuanNode = head => {
    if (!head || !head.next) return null;
    let p1 = head.next;
    let p2 = head.next.next;
    // 判断是否有环，若有环最终两个指针肯定会相交
    while (p1 !== p2) {
      if (!p2 || !p2.next) return null;
      p1 = p1.next;
      p2 = p2.next.next;
    }
    // 获取环的长度
    let length = 1;
    let tNode = p1;
    p1 = p1.next;
    while (p1 !== tNode) {
      length++;
      p1 = p1.next;
    }
    // 从头指针开始，根据长度来获取环的起点
    p1 = head;
    p2 = head;
    while (length !== 0) {
      p2 = p2.next;
      length--;
    }
    while (p1 !== p2) {
      p1 = p1.next;
      p2 = p2.next;
    }
    return p1;
  }
  

两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

答案

  const getCommonNode = (aHead, bHead) => {
    if (!aHead || !bHead) return null;
    const aLen = getLinkLength(aHead);
    const bLen = getLinkLength(bHead);
    let long, short, diff;
    if (aLen > bLen) {
      long = aHead;
      short = bHead;
      diff = aLen - bLen;
    } else {
      long = bHead;
      short = aHead;
      diff = bLen - aLen;
    }
    while (diff--) {
      long = long.next;
    }
    while (long) {
      if (long === short) return long;
      long = long.next;
      short = short.next;
    }
    return null;
  }
  const getLinkLength = head => {
    let length = 0;
    let currentNode = head;
    while (currentNode) {
      length++;
      currentNode = currentNode.next;
    }
    return length;
  }
  

圆圈中最后剩下的数字

0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字，求出这圆圈中剩下的最后一个数字。

答案

  const getLastNode1 = (n, m) => {
    if (!n || !m) return -1;
    const head = {
      val: 0,
      next: null
    }
    let currentNode = head;
    for (let i = 1; i < n; i++) {
      let tempNode = {
        val: i,
        next: null
      }
      currentNode.next = tempNode;
      currentNode = tempNode;
    }
    currentNode.next = head;
    currentNode = head;
    while (currentNode.next !== currentNode) {
      for (let i = 1; i < m; i++) {
        currentNode = currentNode.next;
      }
      currentNode.next = currentNode.next.next;
    }
    return currentNode.val;
  }
  const getLastNode2 = (n, m) => {
    if (!n || !m) return -1;
    const arr = [];
    for (let i = 0; i < n; i++) {
      arr[i] = i;
    }
    let index = 0;
    while (arr.length > 1) {
      index = (index + m) % arr.length - 1;
      if (index >= 0) {
        arr.splice(index, 1);
      } else {
        arr.splice(arr.length - 1, 1);
        index = 0;
      }
    }
    return arr[0];
  }
  const getLastNode3 = (n, m) => {
    if (!n || !m) return -1;
    return handleLastNode2(n, m);
  }
  const handleLastNode3 = (n, m) => {
    if (n === 1) return 0;
    return (handleLastNode3(n - 1, m) + m) % n;
  }
  

删除链表中的节点

给定单链表的头指针和要删除的指针节点，在O(1)时间内删除该节点。

答案

  const deleteNode = (head, node) => {
    if (node.next) { // 若指针不是尾指针时，直接拿下一个指针覆盖即可
      node.val = node.next.val;
      node.next = node.next.next;
    } else if (node === head) { // 若指针是尾指针且只有一个指针时，直接设为空即可
      node = null;
      head = null;
    } else { // 尾指针且不止一个指针时，只能从头遍历，但是也就只能出现1/n次，因为它是尾元素，因此可以间接达到O(1)时间
      node = head;
      while (node.next.next) {
        node = node.next;
      }
      node.next = null;
      node = null;
    }
    return node;
  }
  

删除链表中重复的节点

给定一个单链表，删除出现次数大于1的节点。

答案

  const deleteRepeatNode1 = (head) => {
    if (!head || !head.next) return head;
    let currentNode = head;
    if (currentNode.val === currentNode.next.val) {
      let tempNode = currentNode.next;
      while (tempNode === currentNode.val) {
        tempNode = tempNode.next;
      }
      return deleteRepeatNode1(tempNode);
    } else {
      head.next = deleteRepeatNode1(head.next);
      return head;
    }
  }