链表

[18888628835]

链表

本文的源码可通过这里查看

链表类源码

链表是什么

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

链表的一个好处是，在添加或者删除元素的时候，不需要移动其他元素，这一点数组就做不到。

链表的操作需要用到指针，访问数组时，可以随机访问其中一个元素（通过索引），而链表的访问元素需要从起点（表头）开始迭代链表直到找到所需的元素。

链表的增删改查可以抽象成现实中的火车，当我们需要往里面增加一列车厢时，需要断开两节车厢之间的连接，然后把车厢放进去，重新接上就可以了。

下面我们手动实现链表的 class类，在实现这个类前，我们需要先实现一个能够创建节点的类。

class CreateNode {
  element;
  next;
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

然后开始搭建链表的类函数，以下是一个骨架

class LinkedList {
  count = 0; //链表的元素数量
  head: any = null; //保存第一个元素的引用
  constructor() {}
}

尾部添加元素

要往尾部添加元素，这里有两种场景：

第一种是链表中没有元素，那么我们创建的就是头元素。

第二种是链表中有头元素，那么我们需要遍历到链表的最后一个元素，然后在它的尾部添加一个元素。如何判断尾部呢？链表的最后一个元素的 next 属性指向的是 undefined或者 null（这里我们用 null）。我们通过这个就可以判断其为尾元素。

那么我们就可以实现 push 函数

  //链表最后元素添加新元素
  push(element) {
    let node = new CreateNode(element);
    let current; //当前引用的指针
    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.count += 1;
  }

首先我们根据传入的元素创建一个新的 node 节点，然后进行判断：

如果当前不存在 head，那么创建的 node 节点就变成 head。

如果当前存在 head，那么需要遍历得到最后一个元素，把创建的节点连接到最后一个元素的 next 上。

如何遍历呢？方法是创建一个指针current，首先指向 head 节点， 如果 head 节点的 next 不为 null，那么就不是最后一个元素，我们让这个指针再指向下一个元素（当前指针所在元素的 next）即可。

从特定位置删除元素

链表的索引跟数组是一致，都是从0开始，head 位置指向的就是第0个位置。

const LinkedList ={
  count: 2,
  head: {
    element: 0,
    next: { element: 1, next: null }
  }
}

上面的链表中的 element 的值跟索引是一致的。

下面我们实现一个 removeAt 方法，通过传入索引（index）来移除在该位置的元素。

  //从链表的指定索引移除一个元素。
  removeAt(index) {
    //空链表或者传入位置大于等于链表的节点数量或者小于0，都直接不操作
    if (this.head === null || index >= this.count || index < 0) {
      return null;
    }
    //如果index 是0，则将head 引用直接改为其next
    if (index === 0) {
      this.head = this.head.next;
    } else {
      let current = this.head;
      let previous; //记录要删除元素位置的上一个元素
      for (let i = 0; i < index; i++) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next; //上一个元素的 next 连接到下一个元素的 next，current 就没了
      this.count -= 1;
    }
  }

访问链表的指定位置

区别于数组的随机访问，链表的随机访问需要用循环遍历到指定位置，所以它的时间复杂度为 O(n)，下面实现一个函数能够访问到指定 index 的链表元素。

  //返回链表中特定位置的元素,如果不存在，返回 undefined
  getElementAt(index) {
    if (index >= this.count || index < 0) {
      return undefined;
    }
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }

在任意位置插入元素

下面，我们需要能够在任意位置插入元素:

//链表的特定位置插入一个新元素
  insert(index, element) {
    //首先，我们需要验证 index 是否在范围内，即小于 等于节点数，大于等于0。
    if (index <= this.count && index >= 0) {
      let node = new CreateNode(element);
      //我们还需要考虑head节点，当 index 为0时，头节点就要指向新传入的元素，新元素的 next 需要指向原来 head 节点。
      if (index === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        //考虑完头节点，就可以使用写好的`getElementAt`方法将分别获取指定位置的上一个元素节点，以及指定位置的当前元素节点，让上一个元素节点的 next 指向 新创建的 node，新创建的 node节点的 next 指向当前元素节点就完成了插入操作。
        let previous = this.getElementAt(index - 1);
        let current = previous.next;
        previous.next = node;
        node.next = current;
      }
      this.count += 1;
      return true;
    }
    return false;
  }

头节点插入操作

中间或者尾部添加元素

leetcode 关于链表的题目

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]
 

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

题目解析：

如果要遍历链表，最好在链表的头部添加一个节点，这样可以有效减少边界条件，有助于帮助我们整理思路

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  let root = new ListNode(); //创建一个根节点
  root.next = head; //根节点的后面是头节点
  let previous = root; //指针 previous 指向 root 节点
  let current = head; //指针 current 指向头节点
  //当 current指针一直存在时遍历
  while (current) {
    //   如果当前遍历的节点的 val 等于 val，
    if (current.val === val) {
      // 刚开始时让保存着 root 节点的 previous 的 next 指向下一个
      previous.next = current.next;
    } else {
      //如果判断不成立，那么previous 节点脱离 root 的引用，变成 current 节点
      //当下次循环的时候，previous 就变成了current 节点的上一个节点
      previous = current;
    }
    // current 指针随着遍历一直改变到下一个
    current = current.next;
  }
  return root.next;
};

删除链表元素很简单，当当前指针的 val 等于 val 时，就让上一个指针previous的 next 指向当前current指针的 next节点，切掉上层节点的连接就可以了。

如何获取 previous 指针呢？一个非常简单取巧的方法是新建一个虚拟的节点 root，连接到 head 节点上，然后让 previous 指针指向root 节点。这样每次遍历时，previous 总是在 current 之上。

这种方式很方便让我们获取 previous 指针，无需增加思维负担，思路简洁清晰。我们只需要有个印象，下次循环链表时，可以采取这样简单的方式。

反转链表

反转链表是一个经典的链表题，最简单的思路是采用栈来实现反转，以下是题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

使用栈实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**反转链表
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let current = head;
  let array = [];
  let root = new ListNode();
  let previous = root;
  while (current) {
    array.push(current);
    current = current.next;
  }
  let len = array.length;
  for (let i = 0; i < len; i++) {
    previous.next = array.pop();
    previous = previous.next;
  }
  previous.next = null; //最末尾时指针 pre.next 要手动指向 null，手动解除原来的引用关系
  return root.next;
};

使用栈实现非常简单清晰，很多反转的题目都可以用栈实现，这里就不多解释了。
使用双指针：

双指针解题思路：

定义两个指针：pre在后，cur在前，一次走一步，直到cur为null，即到链表尾部
每次让 cur 的 next 指向 pre ，完成一次局部反转
pre指向cur，cur指向cur的下一个节点，即前进一步

var reverseList = function (head) {
  let root = null; //创建 root节点，由于链表的末尾元素是 null，这里就是 null
  let current = head;
  while (current) {
    let nextTemp = current.next; //先记住 next 节点以免丢失
    current.next = root; //current.next 指向 root
    root = current; //root指针 往前走一位
    current = nextTemp; //current 指针往前走一位
  }
  return root;
};