2. 链表

203. 移除链表元素

203. 移除链表元素
0505，easy，answer

设置一个虚拟头指针，用来解决如果 head 结点要删除时，需要移动 head 的特殊情况。

var removeElements = function (head, val) {
  // 虚拟头节点
  const res = new ListNode(0, head);
  let cur = res;
  while(cur.next) {
    if (cur.next.val === val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return res.next;  // 返回虚拟头节点指向的下一个指针。
};

707. 设计链表

707. 设计链表
0505，mid，answer
链表的定义，链表的处理

错误：找了很久的错误：

// ❗️拼写错误要注意
this._tail  // 写成了 this.tail
this._head  // 写成了 this_head 

// 要注意边界问题，每一个函数在开始是，都要考虑到现处理边界情况。

需要先自定义三个方法（对象）：

定义公共方法：

// 创建一个单链表的结点
class LinkNode {
  constructor(val, next) {
    this.val = val;
    this.next = next || null;
  }
}

// 链表存储：长度、头指针、尾指针
var MyLinkedList = function () {
  this._size = 0;
  this._head = null;
  this._tail = null;
};

// 根据 index 获取链表中的某个节点
MyLinkedList.prototype.getNode = function (index) {
  if (index < 0 || index >= this._size) return null;
  // 如果要最后一个，可以快速定位一下，省去 for 循环
  if (index === this._size - 1) return this._tail;
  let cur = this._head;
  for (let i = 0; i < index; i++) {
    cur = cur.next;
  }
  return cur;
}

答案 (需要加上上面的三个方法)：

// 根据 index 获取链表中的某个节点
MyLinkedList.prototype.getNode = function (index) {
  if (index < 0 || index >= this._size) return null;
  // 如果要最后一个，可以快速定位一下，省去 for 循环
  if (index === this._size - 1) return this._tail;
  let cur = this._head;
  for (let i = 0; i < index; i++) {
    cur = cur.next;
  }
  return cur;
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  if (index < 0 || index >= this._size) return -1;
  // 获取节点值
  return this.getNode(index).val;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  const node = new LinkNode(val, this._head);
  this._size += 1;
  this._head = node;
  // 如果链表中还没结点
  if (this._size === 1)  this._tail = node;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  const node = new LinkNode(val, null);
  this._size += 1;
  // 如果链表中还没结点
  if (this._size === 1) {
    this._head = node;
    this._tail = node;
    return
  }
  this._tail.next = node;
  this._tail = node;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index > this._size) return;
  // 头插入
  if (index <= 0) this.addAtHead(val);
  // 尾插入
  else if (index === this._size) this.addAtTail(val);
  // 正常插入
  else {
    const pre = this.getNode(index - 1);   // 找到要插入的index的前一个结点
    pre.next = new LinkNode(val, pre.next);
    this._size += 1;
  }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || index >= this._size) return;
  // 处理头节点
  if (index === 0) {
    this._head = this._head.next;
    this._size -= 1;
    // 如果链表中没有结点了，额外处理尾结点
    if (this._size === 0) this._tail = null;
    return;
  }
  // 按照 index 查找前一个结点
  const pre = this.getNode(index - 1);
  pre.next = pre.next.next;
  // 处理尾结点
  if (index === this._size - 1) this._tail = pre;
  this._size -= 1;
};

206. 反转链表

206. 反转链表
0505，easy，quick

方法一：双指针

pre 指向前一个结点，cur 指向当前要修改的结点，temp 作为临时结点，指向 cur.next。

var reverseList = function (head) {
  let [pre, cur] = [null, head];
  while (cur) {
    const temp = cur.next;
    cur.next = pre;
    // pre、cur 往前移动
    [pre, cur] = [cur, temp];
  }
  return pre;
};

方法二：迭代

逻辑和双指针是一样的。

var reverseList = function (head) {
  return reverse(null, head);

  function reverse(pre, cur) {
    // 结束递归
    if (!cur) return pre;
    const temp = cur.next;
    cur.next = pre;
    return reverse(cur, temp);
  }
};

方法三：栈

如果要求不原地修改，而是重新构建一个 nodeList 则使用栈结构来复制：

var reverseList = function (head) {
  const stack = [];
  const resList = new ListNode();
  // 原链表的 val 全部入栈：
  for (let cur = head; cur !== null; cur = cur.next) {
    stack.push(cur.val);
  }
  // 将栈中的 val 写入新链表中:
  for (let cur = resList; stack.length; cur = cur.next) {
    cur.next = new ListNode(stack.pop());
  }
  return resList.next;
};

24. 两两交换链表中的节点

24. 两两交换链表中的节点
0505，mid，quick

方法一：三指针

交换链表，需要改动 3 处结点的 .next 关系，也就是说需要三个指针。

需要定义一个虚拟头指针，以解决 head 结点也需要移动的问题；
可以自己画个图，就明白逻辑了。
时间复杂度：O(n)，空间复杂度：O(1)。

一共有三步，但顺序可以反过来：

var swapPairs = function (head) {
  if (!head || !head.next) return head;
  // 虚拟头节点
  const res = new ListNode('', head);
  
  // cur 指向两个被交换节点前的一个结点
  // 交换两个结点：change 和 change.next (也就是temp).
  let [cur, change] = [res, head];
  
  while (change && change.next) {
    const temp = change.next;
    change.next = temp.next;	// 步骤三
    temp.next = change;		// 步骤二
    cur.next = temp;		// 步骤一
    // 指针往前移动
    cur = change;
    change = change.next;
  }
  return res.next;
};

方法二：迭代

// 返回，head 和 head.next 完成交换的链表
var swapPairs = function (head) {
  if (!head || !head.next) return head;

  // newNode 是后面交换好的链表
  const newNode = swapPairs(head.next.next);

  // head 和 head.next(temp) 交换位置，交换后链表头就是tamp了，所以return temp。
  const temp = head.next;
  temp.next = head;
  head.next = newNode;
  return temp;
};

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

19. 删除链表的倒数第 N 个结点
0505，mid，quick

双指针 / 快慢指针：

left 和 right。right 在 left 的右边，与 left 一直保持 n 的距离。
right 从 index = n 开始向后遍历，直到遍历到链表的结尾为止，
- 此时 right 则指向了待删除节点的前一个结点，也就是说 left.next 结点即将被删除；
⚠️ 栈结构也可以，先把所有节点放入栈中，然后向外取 n 个节点，则正好取出带删除节点的前一个节点。

var removeNthFromEnd = function (head, n) {
  res = new ListNode('', head);  // 虚拟头
  let [left, right] = [res, res];

  // right 指针先走 n 个距离
  for (let i = 0; i < n; i++)  right = right.next;
  
  // left 和 right 一起走，直到 right 指向链表尾
  while (right.next) {
    [left, right] = [left.next, right.next];
  }

  // 此时 left 指向带删除节点的前一个结点
  left.next = left.next.next;

  return res.next;
};

面试题 02.07. 链表相交

面试题 02.07. 链表相交
0505，easy，answer
双指针

错误原因：

这里涉及到当变量有点多：有两个链表、两个指针、两个长度。所以需要对每一个操作步骤仔细核对。我就是在其中有很多小错误：
- 变量没有定义直接使用；
- while 循环时，只移动了变量 a，没有移动变量 b；
- 已经定义了一个变量 curL，再后面把 curL 改名时，没有对所有的 curL 全部更换名字。

方法一：双指针｜求长度

求两个链表交点节点的指针。交点不是数值相等，而是指针相等。所以在一个链表上，可能存在多个相同值的节点。

先求出两个链表各自的长度，并求出两个链表长度的差值 gap。
代码中， curA 永远指向更长的一个链表，此时让 curA 移动到，和 curB 末尾对齐的位置，也就是向后移动 gap 个距离。
然后就可以用 while 循环，同时遍历 curA 和 curB 了，当他们两个相等时，则表明指向了同一个节点，返回即可。

时间复杂度：两次获得链表的长度：O(m+n)，然后从头遍历一次链表：O(m) ==> O(m + 2n) 假设 n 为更短的一边

var getIntersectionNode = function (headA, headB) {
  // 拿到更短的一个, lenA is longer
  let [lenA, lenB] = [getLen(headA), getLen(headB)];
  if (lenA < lenB) {
    [lenA, lenB] = [lenB, lenA];
    [headA, headB] = [headB, headA];
  }
  let gap = lenA - lenB;

  // 对长链表进行移动
  let [curA, curB] = [headA, headB];
  while (gap-- > 0) curA = curA.next;

  while (curA) {
    if (curA === curB) return curA;
    curA = curA.next;
    curB = curB.next;
  }
  return null;

  // 获取链表的长度：时间复杂度 O(n)
  function getLen(list) {
    let len = 0, cur = list;
    while (cur) {
      cur = cur.next;
      len++;
    }
    return len;
  }
};

方法二：双指针｜数学思维

总结数学规律：🔗.

时间复杂度：O(a+b) 空间复杂度：O(1)。节点指针 A , B 使用常数大小的额外空间。

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }
    let pA = headA, pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
        console.log(pA, pB);
    }
    return pA;
};

方法三：Set｜哈希集合

利用 Set 只能保存唯一 value ，且有序来确定是否指向同一节点。
流程：
1. 把 headA 中所有节点放入 set 中（O(n)）；
2. 把从头遍历 headB，直到发现 cur 和 set 已经保存的某个指针指向同一个节点，证明从这个节点开始后面都是重复的。O(m)
3. 返回找到的节点。
时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 head 和 headB 的长度。需要遍历两个链表各一次。

空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。

var getIntersectionNode = function(headA, headB) {
    const set = new Set();
    let cur = headA;
    while (cur !== null) {
        cur.add(cur);
        cur = cur.next;
    }
    cur = headB;
    while (cur !== null) {
        if (cur.has(cur)) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
};

142. 环形链表 II

142. 环形链表 II
0506，mid，quick

方法一：Set｜哈希集合

和上题（面试题 02.07.）的方法三一样，使用 set 哈希集合来解决找多指针指向同一节点的问题。

Set 具有两个特点：成员仅有 value 且唯一；成员有序且按照加入时间排序。

var detectCycle = function (head) {
  const set = new Set();
  let cur = head;
  while (cur) {
    if (set.has(cur)) return cur;
    set.add(cur);
    cur = cur.next;
  }
  return null
};

方法二：快慢指针

具体可以看这里。

简单说，就是 fast 一次两步，slow 一次一步。

判断是否有环（图一）：如果 fast 和 slow 相遇，就是有环；
判断环的入口（图二）：从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

var detectCycle = function (head) {
  if (!head || !head.next || !head.next.next) return null;

  // 判断环形
  let [slow, fast] = [head.next, head.next.next];  // ❗️注意，这里先走一步，不能 [head, head.next] 这样不算完整的一步
  while (slow !== fast) { 
    if (!fast.next || !fast.next.next) return null;  // 遍历到链尾，当前环形不存在
    slow = slow.next;
    fast = fast.next.next;
  }

  // 判断入口 slow 从头走， fast 从交点往后走
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
};

======= experience =============================================

链表、带有 index 操作的题：

在 iPad 上简单的绘制流程图，和 code，可以使调理更清晰。

======= summary 1 =============================================

Map 和 Set 的区别：

Set 和 Array 类似，没有 key，只有 value。与 array 不同的是，Set 的 key 是唯一的。
Map 和 Object 类似，有 key 和 value。与 Object 不同的是，Map 的 key 不仅仅是 string、symbol，还可以是任何类型。

关于 Set、Map 的操作 API 和迭代方式：

MDN: Set

MDN: Map

记录几个特殊的：

迭代通常用 for ... of，Map 和 Set 使用方法相同。
- for (const key of myMap.keys()、
- for (const value of myMap.values()、
- for (const [key, value] of myMap.entries())、
增加一个成员有不同：Map.set()、Set.add();

问：js 里面 Map 和 Set 存 / 取的时间复杂度？

Map 和 Set 仅仅作为 JS 中的类型出现，并没有所谓的规范源码，其实现完全取决于各家浏览器的 JS 引擎怎么做。

虽然浏览器的实现没有约束，但是哈希表可以实现O(1)存取时间复杂度，浏览器没理由实现得更差吧。
以 Chrome 的 V8 引擎为例，其有关 Map 的源码在 https://github.com/v8/v8/blob... 中，感兴趣可以自己去阅读。主要运用的是 Hash Table，时间复杂度是 O(1)。
综上，可以认为 map 和 set 的存取时间复杂度都是 O(1)。

我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

Set 就是一个 hash table。

代码随想录：哈希表。

2. 两数相加

2. 两数相加
0613，mid，answer
链表基础

为什么没做出来？

p1、p2 两个指针分别指向两个待相加的链表，当较短的已经遍历完，还需要遍历较长的链表时，

我的处理方案：把较长的链表后续节点直接接到结果 p3 上，然后判断是否需要进位。如果要进位，则再向后遍历每个节点，改变节点的值。
更好的处理方案：不会把较长链表的后续节点直接接在结果链表中，而是令较短链表的值当作 0，当作两个链表都有值，正常的相加和进位。当两个链表都遍历完，判断是否还有进位，有的话创建最后一个节点赋值为 1

var addTwoNumbers = function (l1, l2) {
  // 是否进位
  let nextVal = 0;
  const root = new ListNode(0, null);
  let p1 = l1, p2 = l2, p3 = root;

  while (p1 || p2) {
    // console.log(p1.val, p2.val, nextVal);
    // 如果有其中一个为空，则跳过添加该位
    const p1Val = p1 ? p1.val : 0;
    const p2Val = p2 ? p2.val : 0;
    const sum = p1Val + p2Val + nextVal;
    nextVal = sum >= 10 ? 1 : 0;
    p3.next = new ListNode(sum % 10); // 创建当前节点并添加值

    // 重置指针
    p1 = p1?.next;
    p2 = p2?.next;
    p3 = p3.next;
  }
  // 此时l1，l2两个节点都为空，判断如果有进位，则创建最后一个节点赋值为1；
  if (nextVal) p3.next = new ListNode(1);

  return root.next;
};

21. 合并两个有序链表

21. 合并两个有序链表
0619，easy，quick
链表基础

方法一：迭代

要点：

head 需要创建一个空白链表头，剩下的节点就不需要 new nodeList 创建新链表了，只需要 cur = p1 / p2 赋值整个链表节点。

var mergeTwoLists = function (list1, list2) {
  if (!list1) return list2;
  const head = new ListNode();
  let cur = head;
  let p1 = list1;
  let p2 = list2;

  while (p1 && p2) {
    if (p1.val < p2.val) {
      cur.next = p1;
      p1 = p1.next;
    } else {
      cur.next = p2;
      p2 = p2.next;
    }
    cur = cur.next;
  }
  // 有一个到头了
  if (!p1 || !p2) cur.next = !p1 ? p2 : p1;
  return head.next;
};

方法二：递归

定义递归函数返回值

mergeTwoLists 函数的返回值，就是一个已经合并好的有序链表。

定义递归截止

当 list1 和 list2 有一个链表达到了末尾，则直接返回另一个链表的剩余节点即可。

定义递归逻辑

函数永远返回的链表头节点一定是对小的：

如果 list1 更小，则当前 mergeTwoLists 返回 list1 节点。
在返回之前，给 list1.next 后续链表节点排序合并，递归调用 mergeTwoLists(l1.next, l2); 即可。

var mergeTwoLists = function (l1, l2) {
  // 有一个节点为空
  if (!l1) return l2;
  if (!l2) return l1;

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

203. 移除链表元素​

707. 设计链表​

206. 反转链表​

方法一：双指针​

方法二：迭代​

方法三：栈​

24. 两两交换链表中的节点​

方法一：三指针​

方法二：迭代​

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

面试题 02.07. 链表相交​

方法一：双指针｜求长度​

方法二：双指针｜数学思维​

方法三：Set｜哈希集合​

142. 环形链表 II​

方法一：Set｜哈希集合​

方法二：快慢指针​

2. 两数相加​

21. 合并两个有序链表​

方法一：迭代​

方法二：递归​

203. 移除链表元素

707. 设计链表

206. 反转链表

方法一：双指针

方法二：迭代

方法三：栈

24. 两两交换链表中的节点

方法一：三指针

方法二：迭代

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

面试题 02.07. 链表相交

方法一：双指针｜求长度

方法二：双指针｜数学思维

方法三：Set｜哈希集合

142. 环形链表 II

方法一：Set｜哈希集合

方法二：快慢指针

2. 两数相加

21. 合并两个有序链表

方法一：迭代

方法二：递归