简单

21. 合并两个有序链表

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解：

递归

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
  if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

复杂度分析

时间复杂度：O(n+m)

空间复杂度：O(n+m)

迭代

var mergeTwoLists = function(l1, l2) {
  const prehead = new ListNode(-1);
  let prev = prehead;
  while (l1 != null && l2 != null) {
      if (l1.val <= l2.val) {
          prev.next = l1;
          l1 = l1.next;
      } else {
          prev.next = l2;
          l2 = l2.next;
      }
      prev = prev.next;
  }
  // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
  prev.next = l1 === null ? l2 : l1;
  return prehead.next;
};

复杂度分析

时间复杂度：O(n+m)
空间复杂度：O(1)
141.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

例 1：

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

例 2：

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

示例 3：

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

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

题解：

中间变量

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  // 使用对象Map也可以
  let cycle = new Set();
  while (head) {
    if (cycle.has(head)) {
      return true;
    } else {
      cycle.add(head);
    }
    head = head.next;
  }
  return false;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

快慢指针

var hasCycle = function (head) {
// 操作跑圈，只要是一个圈，跑的快的，一定会把跑的慢的套圈
let slow = head;
let fast = head;
while (fast && fast.next) {
  fast = fast.next.next;
  slow = slow.next;
  if (fast === slow) {
    return true;
  }
}
return false;
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)
142.环形链表2
序号：142
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

例 1：

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

例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

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

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

题解：

中间变量

/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
  // 使用对象Map也可以
  let cycle = new Set();
  while (head) {
    if (cycle.has(head)) {
      return head;
    } else {
      cycle.add(head);
    }
    head = head.next;
  }
  return null;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

快慢指针

var hasCycle = function (head) {
// 操作跑圈，只要是一个圈，跑的快的，一定会把跑的慢的套圈
let slow = head;
let fast = head;
let start = head;
while (fast && fast.next) {
  fast = fast.next.next;
  slow = slow.next;
  if (fast === slow) {
    while (slow && start) {
        if (slow === start) {
        return slow;
      }
      slow = slow.next;
      start = start.next;
    }
  }
}
return null;
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)
203.移除链表元素
给你一个链表的头节点 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
输出：[]
```
题解：
递归
对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；如果 head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head。上述过程是一个递归的过程。

递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于val 并决定是否要删除 head。

var removeElements = function(head, val) {
    if (head === null) {
      return head;
  }
  headt.next = removeElement(head.next, val);
  return head.val === val ? head.next: head;
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。递归过程中需要遍历链表一次。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈，最多不会超过 n 层。

迭代

var removeElements = function(head, val) {
  // 哨兵=>a=>b=>c=>d
  let ele = {
    next: head
};
let cur = ele;
while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
  } else {
      cur = cur.next;
  }
}
return ele.next;
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。

206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1:
```
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
```
示例2：
```
输入：head = [1,2]
输出：[2,1]
```
示例3:
```
输入：head = []
输出：[]
```
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题解：

迭代

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  // 解构
  // [curr.next, prev, curr] = [prev, curr, next];
    let curr = head;
  let prev = null;
  while (curr !== null) {
      let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

复杂度分析

时间复杂度：O(n)，其中 n是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。

递归

var reverseList = function(head) {
  if (head == null || head.next == null) {
      return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
困难
2. 两数相加
序号：2
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9

题目数据保证列表表示的数字不含前导零

模拟

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值 carry，则它们的和为 n1+n2+carry；
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 00 。
此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

var addTwoNumbers = function(l1, l2) {
  let head = null, tail = null;
  let carry = 0;
  while (l1 || l2) {
      const n1 = l1 ? l1.val : 0;
      const n2 = l2 ? l2.val : 0;
      const sum = n1 + n2 + carry;
      if (!head) {
          head = tail = new ListNode(sum % 10);
      } else {
          tail.next = new ListNode(sum % 10);
          tail = tail.next;
      }
      carry = Math.floor(sum / 10);
      if (l1) {
          l1 = l1.next;
      }
      if (l2) {
          l2 = l2.next;
      }
  }
  if (carry > 0) {
      tail.next = new ListNode(carry);
  }
  return head;
};

链表

简单

21. 合并两个有序链表

递归

迭代

141.环形链表

中间变量

快慢指针

142.环形链表2

中间变量

快慢指针

203.移除链表元素

递归

迭代

206.反转链表

迭代

递归

困难

2. 两数相加

模拟