链表的概念和用途

链表的概念和用途

• 数组不是组织数据的最佳结构。

• JavaScript 的数组被实现成了对象，与其他语言的数组相比，效率低了很多。

• 如果你发现数组实际使用很慢，就可以考虑用链表替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的地方。

链表的一些关键点

• 链表是由一系列节点组成的集合，每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。

• 链表元素靠相互之间关系进行引用 A -> B -> C，B 并不是链表的第二个元素而是 B 跟在 A 后面。遍历链表就是跟着链表，从链表的首节点一直到尾节点，但不包含头节点，头节点常常被称为链表的接入点。（链表的尾节点指向一个 null 节点）

• 向单向链表插入一个节点，需要修改它前面的节点（前驱）使其指向新加入的节点，而新加入的节点则指向原来前驱节点指向的节点。

• 从单向链表删除一个节点，需要将待删除节点的前驱节点指向待删除节点的后继节点，同时删除的节点指向 null 节点。

单向链表的代码实现

// 节点类
function Node(data) {
  this.data = data;
  this.next = null;
}

// 链表类
function LinkList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.findPrev = findPrev;
  this.remove = remove;
  this.display = display;
}

// 找到当前节点
function find(data) {
  var currentNode = this.head;
  while (currentNode.data !== data) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

// 在当前节点之后插入新节点
function insert(newData, data) {
  var newNode = new Node(newData);
  var currentNode = this.find(data);
  newNode.next = currentNode.next;
  currentNode.next = newNode;
}

// 找到当前节点的前驱节点
function findPrev(data) {
  var currentNode = this.head;
  while (currentNode.next && currentNode.next.data !== data) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

// 删除某个节点
function remove(data) {
  var prevNode = this.findPrev(data);
  var currentNode = this.find(data);
  if (prevNode.next) {
    prevNode.next = currentNode.next;
    currentNode.next = null; // 释放内存，防止内存泄漏
  }
}

// 打印整个链表
function display() {
  var currentNode = this.head;
  var linkArr = [];
  while (currentNode.next) {
    // 打印链表时不需要打印头节点
    linkArr.push(currentNode.next.data);
    currentNode = currentNode.next;
  }
  console.log(linkArr.join(" -> "));
}

var link = new LinkList();
link.insert("first", "head");
link.insert("second", "first");
link.insert("third", "second");
link.display(); // first -> second -> third
link.remove("second");
link.display(); // first -> third

双向链表的代码实现

// 节点类
function Node(data) {
  this.data = data;
  this.prev = null;
  this.next = null;
}

// 链表类
function LinkList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
  this.findLast = findLast;
  this.displayReverse = displayReverse;
}

function find(data) {
  var currentNode = this.head;
  while (currentNode.data !== data) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

// 在当前节点之后插入新节点，分尾节点和非尾节点两种情况
function insert(newData, data) {
  var newNode = new Node(newData);
  var currentNode = this.find(data);
  // 如果新节点插入的位置是尾节点
  newNode.next = currentNode.next;
  newNode.prev = currentNode;
  currentNode.next = newNode;
  // 如果新节点插入的位置不是尾节点
  if (newNode.next) {
    newNode.next.prev = newNode;
  }
}

// 删除某个节点，也分尾节点和非尾节点两种情况
function remove(data) {
  var currentNode = this.find(data);
  if (currentNode.next) {
    // 如果删除的节点不是尾节点
    currentNode.prev.next = currentNode.next;
    currentNode.next.prev = currentNode.prev;
    // 释放内存，防止内存泄漏
    currentNode.prev = null;
    currentNode.next = null;
  } else {
    // 如果删除的节点是尾节点
    currentNode.prev.next = null;
    currentNode.prev = null; // 释放内存，防止内存泄漏
  }
}

// 打印整个链表
function display() {
  var currentNode = this.head;
  var linkArr = [];
  while (currentNode.next) {
    // 打印链表时不需要打印头节点
    linkArr.push(currentNode.next.data);
    currentNode = currentNode.next;
  }
  console.log(linkArr.join(" < == > "));
}

// 找到最后一个节点
function findLast() {
  var currentNode = this.head;
  while (currentNode.next) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

// 反向打印整个链表
function displayReverse() {
  var currentNode = this.findLast();
  var linkArr = [];
  while (currentNode.prev) {
    linkArr.push(currentNode.data);
    currentNode = currentNode.prev;
  }
  console.log(linkArr.join(" < == > "));
}

var link = new LinkList();
link.insert("first", "head");
link.insert("second", "first");
link.insert("third", "second");
link.display(); // first < == > second < == > third
link.remove("second");
link.display(); // first < == > third
link.displayReverse(); // third < == > first

链表的另外两种实现

// 定义链表类
function LinkList() {
  // 定义节点
  var Node = function(data) {
    this.data = data;
    this.next = null;
  };
  var length = 0; // 长度
  var head = null; // 头节点
  var tail = null; // 尾节点

  // 链表尾部添加一个节点
  this.append = function(data) {
    // 创建新节点
    var new_node = new Node(data);
    if (head === null) {
      head = new_node;
      tail = new_node;
    } else {
      tail.next = new_node;
      tail = new_node;
    }
    length++;
    return true;

    // 另一种实现方式
    // var node = new Node(data);
    // if (head == null) {
    //   head = node;
    // } else {
    //   var current = head;
    //   while (current.next) {
    //     current = current.next;
    //   }
    //   // while 循环执行完之后 ，current 已经是链表最后一项了
    //   current.next = node;
    // }
    // length++;
  };

  //打印链表
  this.print = function() {
    var curr_node = head;
    var linkArr = [];
    while (curr_node) {
      // console.log(curr_node.data);
      linkArr.push(curr_node.data);
      curr_node = curr_node.next; //遍历链表的核心
    }
    console.log(linkArr.join(" -> "));
  };

  //任意位置插入节点
  this.insert = function(index, data) {
    if (index < 0 || index > length) {
      // index 不合法
      return false;
    } else if (index === length) {
      // index === length,说明是在尾节点的后面新增,直接调用 append 方法即可
      return this.append(data);
    } else {
      var new_node = new Node(data);
      if (index === 0) {
        // 如果在头节点前面插入,新的节点就变成了了头节点
        new_node.next = head;
        head = new_node;
      } else {
        // 要插入的位置是 index，找到索引为 index-1 的节点，然后进行连接
        // var insert_index = 1;
        // var curr_node = head;
        // while(insert_index < index){
        //     insert_index++;
        //     curr_node = curr_node.next;
        // }
        // // index = 1，curr_node 指向 head，是第一个节点，
        // var next_node = curr_node.next;   // next_node 是第二个节点
        // curr_node.next = new_node;        // 第一个节点指向要插入的节点
        // new_node.next = next_node;        // 要插入的节点指向第二个节点

        // 另一种实现方式
        var pre_node = get_node(index - 1);
        new_node.next = pre_node.next;
        pre_node.next = new_node;
      }
      length++;
      return true;
    }
  };

  // 删除指定位置的节点
  this.removeAt = function(index) {
    if (index < 0 || index >= length) {
      // index 不合法
      return null;
    } else {
      var del_node = null; // 存放被删除的节点
      if (index === 0) {
        del_node = head;
        head = head.next;
      } else {
        var del_index = 0;
        var pre_node = null; // 被删除节点的前一个节点
        var curr_node = head; // 被删除的节点
        while (del_index < index) {
          del_index++;
          pre_node = curr_node;
          curr_node = curr_node.index;
        }
        del_node = curr_node;
        // 被删除节点的前一个节点指向被删除节点的后一个节点
        pre_node.next = curr_node.next;
        // 如果被删除的节点是尾节点
        if (curr_node.next === null) {
          tail = pre_node;
        }
      }
      length--;
      del_node.next = null;
      return del_node.data;
    }
  };

  /*
    // 另一种实现方式
    // 删除指定位置的节点
    this.removeAt = function(index) {
      // 参数不不合法
      if (index < 0 || index >= length) {
        return null;
      } else {
        var del_node = null;
        // 删除的是头节点
        if (index == 0) {
          // head 指向下一个节点
          del_node = head;
          head = head.next;
          // 如果 head == null，说明之前链表只有一个节点
          if(!head){
            tail = null;
          }
        } else {
          // 找到索引为 index-1 的节点
          var pre_node = get_node(index-1);
          del_node = pre_node.next;
          pre_node.next = pre_node.next.next;
          // 如果删除的是尾节点
          if(del_node.next==null){
            tail = pre_node;
          }
        }
        length -= 1;
        del_node.next = null;
        return del_node.data;
      }
    };
  */

  // removeAt(index)   删除某个位置的元素
  // indexOf(data)     获取某个元素的位置
  this.remove = function(data) {
    // length --
    return this.removeAt(this.indexOf(data));
  };

  // 获得指定位置的节点
  var get_node = function(index) {
    if (index < 0 || index >= length) {
      return null;
    }
    var curr_node = head;
    var node_index = index;
    while (node_index-- > 0) {
      curr_node = curr_node.next;
    }
    return curr_node;
  };
  // 返回指定位置节点的值
  this.get = function(index) {
    var node = get_node(index);
    if (node) {
      return node.data;
    }
    return null;
  };

  // 返回指定元素的索引，如果没有，返回-1；如果有多个相同元素，返回第一个
  this.indexOf = function(data) {
    var index = -1;
    var curr_node = head;
    while (curr_node) {
      index++;
      if (curr_node.data === data) {
        return index;
      } else {
        curr_node = curr_node.next;
      }
    }
    return -1;
  };

  // 返回链表的大小
  this.length = function() {
    return length;
  };

  // 删除尾节点
  this.remove_tail = function() {
    return this.remove(length - 1);
  };

  // 删除头节点
  this.remove_head = function() {
    return this.remove(0);
  };

  // 返回链表头节点的值
  this.head = function() {
    return this.get(0);
  };

  // 返回链表尾节点的值
  this.tail = function() {
    return this.get(length - 1);
  };

  // 判断链表是否为空
  this.isEmpty = function() {
    return this.length === 0;
  };

  // 清空链表
  this.clear = function() {
    head = null;
    tail = null;
    length = 0;
  };
}

var link = new LinkList();
link.append(1);
link.append(4);
link.append(9);
link.print();
console.log(link.head());

var LikedList = function() {
  // 链表头
  var head = null;
  // 链表长度
  var length = 0;

  // 辅助类：节点
  var Node = function(element) {
    this.element = element;
    this.next = null;
  };

  // 链表尾添加元素
  this.append = function(element) {
    var node = new Node(element);

    if (head == null) {
      head = node;
    } else {
      var current = head;
      while (current.next) {
        current = current.next;
      }
      // while 循环执行完之后 ，current 已经是链表最后一项了
      current.next = node;
    }
    length++;
  };

  // 链表某一个位置添加元素
  this.insert = function(position, element) {
    // 没有越界时
    if (position > -1 && position < length) {
      var node = new Node(element);
      if (position === 0) {
        var current = head;
        head = node;
        head.next = current;
      } else {
        var index = 0;
        var current = head;
        var previous = null;
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }

        previous.next = node;
        node.next = current;
      }
      length++;
    }
  };

  this.removeAt = function(position) {
    if (position > -1 && position < length) {
      if (position === 0) {
        var current = head;
        head = current.next;
      } else {
        var current = head;
        var previous = null;
        var index = 0;
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }
        // 跳出循环的时候 index === position
        previous.next = current.next;
      }

      length--;
      return current;
    }
    return null;
  };

  this.indexOf = function(element) {
    var current = head;
    var index = 0;
    while (current) {
      if (current.element === element) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  };

  // removeAt(position)   删除某个位置的元素
  // indexOf(element)     获取某个元素的位置
  this.remove = function(element) {
    // length --
    return this.removeAt(this.indexOf(element));
  };

  this.isEmpty = function() {
    return length === 0;
  };
  this.size = function() {
    return length;
  };

  this.getHead = function() {
    return head;
  };
};

var l = new LikedList();
l.append(1);
l.append(2);
l.append(3);
l.insert(1, 10);
console.log(l.size());

反转链表 ✅

题目地址 (opens new window)

// 迭代解法，时间复杂度是 O(n)，空间复杂度是 O(1)
var reverseList = function(head) {
  if (!head || !head.next) {
    return head;
  }
  let prev = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};

// 递归解法，时间复杂度和空间复杂度都是 O(n)
// 递归写法虽然更简洁，但调用栈深度为 O(n)，链表很长时有栈溢出风险，迭代是更安全的选择
var reverseList = function(head) {
  if (!head || !head.next) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

反转链表 II

题目地址 (opens new window)

var reverseBetween = function(head, left, right) {
  // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
  const dummy = new ListNode();
  dummy.next = head;

  // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
  let prevLeftNode = dummy;
  for (let i = 0; i < left - 1; i++) {
    prevLeftNode = prevLeftNode.next;
  }

  // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
  let rightNode = prevLeftNode;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }

  // 第 3 步：切断出一个子链表（截取链表）
  let leftNode = prevLeftNode.next;
  let nextRightNode = rightNode.next;

  // 注意：切断链接
  prevLeftNode.next = null;
  rightNode.next = null;

  // 第 4 步：反转子链表
  reverseLinkedList(leftNode);

  // 第 5 步：接回到原来的链表中
  leftNode.next = nextRightNode;
  prevLeftNode.next = rightNode;

  return dummy.next;
};

function reverseLinkedList(head) {
  let prev = null,
    cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
}

两两交换链表中的节点

题目地址 (opens new window)

var swapPairs = function(head) {
  const dummy = new ListNode(null); // 虚拟节点，用于返回最终的结果
  dummy.next = head;
  let prev = dummy; // 虚拟节点，用于协助交换
  while (head && head.next) {
    let first = head,
      second = head.next; // 实际要相互交换位置的两个节点
    prev.next = second;
    first.next = second.next;
    second.next = first;
    prev = first;
    head = first.next;
  }
  return dummy.next;
};

环形链表 ✅

题目地址 (opens new window)

// 时间复杂度是 O(n)，空间复杂度是 O(1) 
var hasCycle = function(head) {
  if (!head || !head.next) {
    return false;
  }
  let slow = head;
  let fast = head.next;
  while (slow !== fast) {
    if (!fast || !fast.next) {
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
};

删除链表的节点

题目地址 (opens new window)

// 递归解法
var deleteNode = function(head, val) {
  if (head.val === val) {
    return head.next;
  }
  head.next = deleteNode(head.next, val);
  return head;
};

// 迭代解法
var deleteNode = function(head, val) {
  if (head.val === val) {
    return head.next;
  }
  let cur = head;
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
      break;
    }
    cur = cur.next;
  }
  return head;
};

// 双指针解法
var deleteNode = function(head, val) {
  if (head.val === val) {
    return head.next;
  }
  let prev = new ListNode(-1);
  let cur = head;
  prev.next = cur;
  while (cur) {
    if (cur.val === val) {
      prev.next = cur.next;
      break;
    }
    prev = prev.next;
    cur = cur.next;
  }
  return head;
};

删除链表中的节点 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(1)
// 解法的巧妙之处在于：不需要真正删除自己，而是把下一个节点 "复制" 过来覆盖当前节点
var deleteNode = function(node) {
  node.val = node.next.val;
  node.next = node.next.next;
};

两数相加 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(max(m,n))
var addTwoNumbers = function(l1, l2) {
  let res = new ListNode();
  let carry = 0;
  let cur = res;
  while (l1 || l2 || carry) {
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    const sum = val1 + val2 + carry;
    carry = sum >= 10 ? 1 : 0;
    cur.next = new ListNode(sum % 10);
    cur = cur.next;
    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
  }
  return res.next;
};

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

题目地址 (opens new window)

// 时间复杂度是 O(n)，空间复杂度是 O(1)
var deleteDuplicates = function(head) {
  if (!head || !head.next) {
    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;
};

合并两个有序链表 ✅

题目地址 (opens new window)

// 递归合并
// 时间复杂度是 O(m + n)，两个链表中的每个节点最多被处理一次
// 空间复杂度是 O(m + n)，递归调用栈最深可能达到两个链表的节点总数
var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    // 递归终止条件：l1 为空时，直接返回 l2 的剩余部分
    return l2;
  } else if (l2 === null) {
    // 递归终止条件：l2 为空时，直接返回 l1 的剩余部分
    return l1;
  } else if (l1.val <= l2.val) {
    // l1 当前节点较小，将它作为当前结果节点
    // 递归合并 l1 的剩余部分和 l2，并连接到 l1 后面
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    // l2 当前节点较小，递归合并 l1 和 l2 的剩余部分
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

// 迭代合并
// 时间复杂度是 O(m + n)，两个链表中的每个节点最多被处理一次
// 空间复杂度是 O(1)，只使用了虚拟头节点和若干指针，并且复用了原链表节点
var mergeTwoLists = function(l1, l2) {
  // 创建虚拟头节点，避免单独处理结果链表的第一个节点
  const dummy = new ListNode();
  // cur 始终指向已合并链表的最后一个节点
  let cur = dummy;

  // 两个链表都不为空时，依次选择较小的节点
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      // 将 l1 当前节点接到结果链表，并让 l1 向后移动
      cur.next = l1;
      l1 = l1.next;
    } else {
      // 将 l2 当前节点接到结果链表，并让 l2 向后移动
      cur.next = l2;
      l2 = l2.next;
    }
    // cur 移动到刚刚接入的节点
    cur = cur.next;
  }

  // 此时至少有一个链表为空，直接接上另一个链表的剩余部分
  cur.next = l1 ? l1 : l2;
  // dummy 不属于结果链表，返回真正的头节点
  return dummy.next;
};

合并 K 个升序链表 ✅

题目地址 (opens new window)

// 顺序合并
// 时间复杂度是 O(kn)，k 为链表数量，n 为所有链表的节点总数
// 空间复杂度是 O(1)，只用了几个指针变量，merge2Lists 复用节点而非新建，不需要额外空间
const merge2Lists = (l1, l2) => {
  const dummy = new ListNode();
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 ? l1 : l2;
  return dummy.next;
};

var mergeKLists = function(lists) {
  let res = null;
  for (let i = 0; i < lists.length; i++) {
    res = merge2Lists(res, lists[i]);
  }
  return res;
};

// 分治合并
// 时间复杂度是 O(nlogk)，n 是所有节点总数，k 是链表条数；递归 logk 层，每层合并总代价 O(n)
// 空间复杂度是 O(logk)，递归调用栈的深度；合并本身复用节点，不占额外空间
const merge2Lists = (l1, l2) => {
  const dummy = new ListNode();
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 ? l1 : l2;
  return dummy.next;
};

var mergeKLists = function(lists) {
  if (lists.length === 0) return null;

  // 分治合并 [left, right] 区间内的链表，返回合并后的一条链表
  const merge = (left, right) => {
    if (left === right) return lists[left]; // 只剩一条，直接返回
    const mid = (left + right) >> 1; // 中点，等价于 Math.floor((left + right) / 2)
    const l1 = merge(left, mid); // 递归合并左半边
    const l2 = merge(mid + 1, right); // 递归合并右半边
    return merge2Lists(l1, l2); // 左右两条合并成一条
  };

  return merge(0, lists.length - 1);
};