回文链表、环形链表、删除链表中的节点

回文链表

请判断一个链表是否为回文链表。

示例

输入: 1->2
输出: false
​
输入: 1->2->2->1
输出: true

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题目分析

• ​$O(n)$的时间复杂度意味着只能遍历一趟链表；

• ​$O(1)$的空间复杂度意味着只能使用常数个变量（也就是不能使用数组、集合等变量）

方法一 字符串拼接比较

思路

通过正向、反向将链表节点值拼接成字符串，最后比较正向、反向字符串是否相同。

详解

1. 定义两个临时变量，存储正、反两个拼接的字符串

2. 遍历链表，进行字符串拼接

3. 比较正、反字符串是否相同

代码

function isPalindrome (head) {
  let positiveStr = '';
  let reverseStr = '';
  while (head) {
    const nodeVal = head.val;
    // 正向字符串拼接
    positiveStr += nodeVal;
    // 反向字符串拼接
    reverseStr = nodeVal + reverseStr;
    // 下一个节点
    head = head.next;
  }
​
  return positiveStr === reverseStr;
}

复杂度分析

• 时间复杂度：$O(n)$ 过程中只会遍历一遍链表，因此，时间复杂度为 $O(n)$。

• 空间复杂度：$O(1)$ 过程中产生 2 个临时变量存储，因此，空间复杂度为 $O(1)$。

方法二 递归解法

思路

通过递归的方式逆序遍历链表，同时定义一个全局变量 pointer 从前往后正序遍历链表，如果正序和逆序遍历出来的值相等，则为回文链表。

详解

1. 首先，定义一个全局变量 pointer 指针，初始化值为头部节点 head，用于正序遍历。

2. 然后，调用递归函数进行链表的逆序遍历，递归出口为 head 为 null，表示链表遍历结束，返回 true。

3. 如果正序遍历的节点值全部都等于逆序遍历的节点值，那么 res 的值一直为 true，则递归结束最后的返回值也为 true，即为回文链表。反之，则 res 为 false，不是回文链表。

代码

let pointer;
​
function reverseLinkList (head) {
  if (!head) return true;
  // 递归逆序遍历
  const res = reverseLinkList(head.next) && (pointer.val === head.val);
  // pointer 指针不断向后指，进行正序遍历
  pointer = pointer.next;
  return res;
}
​
function isPalindrome (head) {
  pointer = head;
  return reverseLinkList(head);
}

复杂度分析

• 时间复杂度：$O(n)$ 过程中只对链表进行了一次遍历，因此，时间复杂度为 $O(n)$。

• 空间复杂度：$O(1)$ 过程中只申请了一个全局变量 pointer，因此，空间复杂度为 $O(1)$。

方法三 快慢指针

思路

找到链表的中间节点，将前半部分的链表反转，与后半部分链表数据进行比较。 为了找到中间位置，采用两个引用，步调速度相差 1，当快的引用到达最终节点时，慢的正好在中间。

详解

1. 分别定义快、慢指针，及前半部分的指针存储

2. 遍历链表，快指针走 2 步，慢指针走 1 步，同时将慢指针对应的前半部分链表进行反转

3. 链表结束后，慢指针指向中间，与前半部分反转的链表进行逐个比较

代码

function isPalindrome (head) {
  // 空或者单节点
  if (!head || !head.next) {
    return true;
  }
​
  let slowRef = head; // 慢指针
  let fastRef = head; // 快指针
  let reverseRef; // 反转前半部分
  let reversePreRef; // 反转前一个节点
  // 连续 2 个节点都存在
  while (fastRef && fastRef.next) {
    // 快指针前进 2 步
    fastRef = fastRef.next.next;
​
    reverseRef = slowRef;
    // 慢指针前进 1 步
    slowRef = slowRef.next;
​
    // 反转链表
    reverseRef.next = reversePreRef;
    // 记录上一个节点
    reversePreRef = reverseRef;
  }
​
  // 奇数场景
  if (fastRef) {
    // 中间值不用比较，慢指针直接前进一步
    slowRef = slowRef.next;
  }
​
  while (reverseRef && slowRef) {
    // 链表逐个值比较
    if (reverseRef.val !== slowRef.val) {
      return false;
    }
    reverseRef = reverseRef.next;
    slowRef = slowRef.next;
  }
  return true;
}

复杂度分析

• 时间复杂度：$O(n)$​

  我们只遍历了包含有 $n$ 个元素的列表一次，因此，时间复杂度为 $O(n)$。

• 空间复杂度：$O(1)$​

  产生 4 个临时变量存储，因此，空间复杂度为 $O(1)$。

环形链表

给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路

环形链表一般分为两种，一是头尾相连的循环链表，二是尾部与中间节点相连的6字型链表。我们如何判断一个链表是否是环形链表呢？不管是哪一种环形链表，循环遍历的时候一定是死循环的，那么在链表循环过程中，如果我们不止一次的遇到同一个节点，这个链表就肯定是环形链表。

最常见的有三种方法判断： 1. 双指针法 2. 哈希表法 3. 利用 Symbol 的特性

方法一 双指针

详解

双指针，即快慢指针。我们定义两个指针，初始位置都是在链表的头部，两个指针同时出发，快指针一次可以前进两步，而慢指针一次只能前进一步。会出现以下几种情况 1. 链表为空，肯定不是环形链表； 2. 链表不为空，快指针走到了链表的结尾，也可以判断不是环形链表； 3. 链表不为空，快指针和慢指针相遇，则证明此链表是环形链表

就像 A 和 B 两个人跑步，A 跑步速度是 B 跑步速度的两倍。两人同时从同一起点开始跑。排除跑道长度为 0 的情况： 1. A 跑到了跑道的尽头，此时 B 在跑道的中间，那么这个跑道肯定不是一个环形跑道。 2. A 和 B 相遇。在 A、B 速度不同的情况下，如果除起点外还可以再次相遇，那么这个跑道，不管是圆形还是6字型，肯定是环形跑道。

代码

/**
 * @param {ListNode} head
 * @return {boolean}
 */
​
const hasCycle = function (head) {
  if (!head) return false;
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) return true;
  }
  return false;
};

复杂度分析

• 时间复杂度：$O(n)$ 对于含有 n 个元素的单向链表，指针移动到尾部的时间为 $O(n)$； 对于含有 n 个元素的环形链表，指针移动的时间为 第一次指针移动到尾部的时间 + 指针再次移动到两指针相遇的节点的时间 = $O(n + m)$，即 $O(n)$；

• 空间复杂度：$O(1)$​

方法二 哈希表

详解

创建一个空 Map 对象并遍历链表中的所有节点，每遍历一个节点，就像空对象里插入一条组键值对为 { 当前节点: 1 }。 1. 如果遍历完成，该 Map 对象中不存在相同节点，那么不是环形链表。 2. 遍历中，发现该 Map 对象中存在相同节点且值为 1，即该节点已经遍历过了，那么链表是环形链表

代码

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = function (head) {
  if (!head) return false;
  const newData = new Map();
  while (head) {
    if (newData.has(head)) return true;
    newData.set(head, 1);
    head = head.next;
  }
  return false;
};

复杂度分析

• 时间复杂度：$O(n)$ 添加一个结点到哈希表中只需要花费 $O(1)$ 的时间。对于含有 $n$ 个元素的链表，将节点添加到哈希表中至少有 $n$ 次，这将耗费 $O(n)$ 的时间。

• 空间复杂度：$O(n)$ 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 $n$ 个元素。

方法三 Symbol

详解

Symbol，表示独一无二的值。ES6中新引入的一种数据类型。

和哈希表不一样的是，哈希表是将遍历过节点存到一个 Map 对象中，若循环到一个节点，且对象中存在该节点，则证明为环形链表。而这个方法是将当前节点的 val 值改为用 Symbol 创建的一个独一无二的值，若链表循环过程中存在节点的 val 全等于这个值，那么证明当前不是第一次循环到该节点，即链表为环形链表，反之不是。

代码

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = function (head) {
  if (!head) return false;
  const newData = Symbol('');
  while (head) {
    if (head.val === newData) return true;
    head.val = newData;
    head = head.next;
  }
  return false;
};

复杂度分析

• 时间复杂度：$O(n)$ 对于含有 n 个元素的链表，循环判断并赋值，这将耗费 $O(n)$ 的时间。

• 空间复杂度：$O(1)$​

删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

4 -> 5 -> 1 -> 9

示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

• 链表至少包含两个节点。

• 链表中所有节点的值都是唯一的。

• 给定的节点为非末尾节点并且一定是链表中的一个有效节点。

• 不要从你的函数中返回任何结果。

方法一

思路

这道题通俗地将就是要删除给定节点。在获取当前节点后，可以将下一个节点的值赋给当前节点，然后将当前节点指向下下个节点，完成删除。

详解

1. node.value = node->next.value

2. node->next=node->next->next

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
const deleteNode = function (node) {
  node.val = node.next.val;
  node.next = node.next.next;
};

复杂度分析

• 时间复杂度：$O(1)$​

  耗时与输入数据大小无关

• 空间复杂度：$O(1)$​

  耗空间与输入数据大小无关

方法二

思路

利用 Js 的 Object.assign() 方法。

Object.assign() 方法用于将所有可枚举属性的值从一个或多个源对象复制到目标对象。它将返回目标对象。简单来说，Object.assign(a,b) 能合并两个对象(a和b)，并覆盖到第一个参数(a)所指的地址上。

由于 Js 的对象都是内存引用，也就是说 node 这个变量里面，只保存了内存地址。因此可以用Object.assign()，使得 node.next 覆盖 node.

详解

将 node 和 node.next 合并，并保存到 node 所指的内存地址上。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
const deleteNode = function (node) {
  Object.assign(node, node.next);
};

复杂度分析

• 时间复杂度：$O(1)$​

  删除节点只改变指针的指向，与数据大小无关。

• 空间复杂度：$O(1)$​

  只对原有的参数空间进行了操作。