用JavaScript实现链表和解决常见的算法题

实现链表

在存储多个元素的时候，我们通常会用数组。但是数组的特性让它有个缺点：插入和删除的效率很慢。因为数组的内存是连续的，这也是它为什么能实现随机读取的原因，也让它永远高效率的读取效率，但是因为内存空间是连续的，所以导致插入和删除是很复杂，平均时间复杂度是O(n)。

而链表就不一样，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。如图所示：

我们用代码来实现：

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

链表的算法题

我们实现了链表的数据结构，那么我们来做几道链表的算法题：

删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

输入：head = [1,1,2]
输出：[1,2]

这道题在LeetCode中算是比较简单，其实能阅读懂问题就能求出答案：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if (!head) {
        return head;
    }
    let cur = head;
    // 迭代第一个元素的下一个元素
    while (cur.next) {
      // 如果下一个元素和当前元素的值相等，把当前元素的下一个指针指向下一个元素的下一个元素，
      // 这相当于删除了元素。
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
 };

时间复杂度是O(n)。
空间复杂度是O(1)。

合并两个有序链表

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

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

这道题有两种解法，其实这道题不算很简单，我们先来看第一种的递归解法：

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(l1 === null){  // 如果l1是null，那么直接返回l2
        return l2
    }else if(l2 === null){    // 如果l2是null，那么直接返回l1
        return l1
    }else if(l1.val < l2.val){    // 如果l1小于l2，传入l1的next和l2递归
        l1.next = mergeTwoLists(l1.next, l2);
        return l1
    }else{
        // 如果l2小于l1，传入l1和l2的next递归
        l2.next = mergeTwoLists(l1, l2.next);
        return l2
    }
};

递归的版本其实比较好理解，基本看代码都能理解。第二种的算法版本则稍微难理解点，第二种是迭代的版本，这个版本是利用设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  // 哨兵节点
  const prehead = new ListNode(-1);

  let prev = prehead;
  // 迭代
  while (l1 != null && l2 != null) {
      // 如果l1小于l2，哨兵的next节点是l1，l1赋值为当前l1的next
      if (l1.val <= l2.val) {
          prev.next = l1;
          l1 = l1.next;
      } else {
      // 如果l2小于l1，哨兵的next节点是l2，l2赋值为当前l2的next
          prev.next = l2;
          l2 = l2.next;
      }
      prev = prev.next;
  }

  // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
  prev.next = l1 === null ? l2 : l1;

  return prehead.next;
};

上面的注释我借用了LeetCode的一些官方解释，结合我自己的注释比较好理解。

时间复杂度是O(m+n)，m、n是分别是两个链表的长度。
空间复杂度是O(1)。

删除链表的倒数第 N 个结点

这道题在LeetCode上难度是中等，我们先来看题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

算法代码：

var removeNthFromEnd = function(head, n) {

  // 获取链表的长度的方法
  function getLength(head){
      let length = 0;
      while(head){
          length++;
          head = head.next;
      }
      return length;
  }

  // 声明一个空节点，空节点的下个节点就是head
  const dummy = new ListNode(0, head);

  const length = getLength(head);

  // 链表往下递推链表长度减去n的次数就是我们要删去的节点的上一个节点
  let current = dummy;
  for(let i = 0; i < length - n ; i++){
      current =  current.next;
  }
  // 直接删除节点
  current.next = current.next.next;
  return dummy.next;
};

这个题目可能有点难以理解，LeetCode官方其实讲的很清楚，下面上图：

dummy就是current，然后length - n 是等于2，所以current是2的那个节点，直接改变next的指针即可。

时间复杂度是O(n)，n是链表的长度。
空间复杂度是O(1)。