链表

反转链表

十分重要的一个技巧，后续很多单链表都会用到

function reverseList(head: ListNode | null): ListNode | null {
    let pre = null, cur = head
    while (cur) {
        const next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}

是否需要创建虚拟头结点

const dummy = new ListNode(0, head)

取决于头结点是否可能被删除，如果可能被删除，需要创建

反转链表二

这题涉及到两个思想

1. 如下，如何把链表节点 E 移动到 A 前

● → ● → ● → ● → ● → ●
A   B   C   D   E   F

如何知道应该改变哪一个 next 指针呢？

答：当前解题指向的点，的前一个节点的 next 指针可以被改变（改变后的next指针应该指向哪里，根据题目需求来）

2. 头插法

头插法是一种创建链表的方式，创建出来的链表是逆序的

比如根据一个数组，按数组顺序 [1, 2, 3] 使用头插法，创建的链表是 3 -> 2 -> 1

function CreateList_Head(head: ListNode, list: number[]) {
    for (const i of list) {
		const node = new ListNode(i)
        node.next = head.next
        head.next = node
    }
    return head
}

由上面两个点，可以得到解法：把 left 指针后的节点（直到 right），循环插入到 pre 前，就可以把 left 和 right 之间的节点反转了

● → ● → ● → ● → ● → ●
p   l           r

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    const temp = new ListNode(0, head)
    let pre = temp
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next
    }
    let cur = pre.next
    for (let i = 0 ; i < right - left; i++) {
        const next = cur.next
        cur.next = next.next
        next.next = pre.next
        pre.next = next
    }
    return temp.next
};

双指针——起点不一致的快慢指针

起点不一致的快慢指针：指的是两个指针从同一侧开始遍历链表，但是两个指针的起点不一样。快指针 fast 比慢指针 slow 先走 n 步，直到快指针移动到链表尾端时为止。

求解步骤

使用两个指针 slow、fast。slow、fast 都指向链表的头节点，即：slow = head，fast = head。
先将快指针向右移动 n 步。然后再同时向右移动快、慢指针。
等到快指针移动到链表尾部（即 fast == None）时跳出循环体。

代码模版

const slow = head, fast = head

for (let i = 0; i < n; i++) {
	fast = fast.next
}

while (fast) {
	fast = fase.next
    slow = slow.next
}

适用范围

主要用于找到链表中倒数第 k 个节点、删除链表倒数第 N 个节点等

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

双指针——步长不一致的快慢指针

步长不一致的快慢指针：指的是两个指针从同一侧开始遍历链表，两个指针的起点一样，但是步长不一致。例如，慢指针 slow 每次走 1 步，快指针 fast 每次走两步。直到快指针移动到链表尾端时为止。

求解步骤

使用两个指针 slow、fast。slow、fast 都指向链表的头节点。
在循环体中将快、慢指针同时向右移动，但是快、慢指针的移动步长不一致。比如将慢指针每次移动 1 步，即 slow = slow.next。快指针每次移动 2 步，即 fast = fast.next.next。
等到快指针移动到链表尾部（即 fast == None）时跳出循环体。

代码模版

const slow = head, fast = head

while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
}

适用范围

适合寻找链表的中点、判断和检测链表是否有环、找到两个链表的交点等问题。

876. 链表的中间结点
141. 环形链表
142. 环形链表 II

双指针——分离双指针

分离双指针：两个指针分别属于不同的链表，两个指针分别在两个链表中移动

求解步骤

使用两个指针 i、j。i 指向第一个链表头节点，即：i = list1，j 指向第二个链表头节点，即：j = list2。
当满足一定条件时，两个指针同时右移，即 i = i.next、j = j.next。
当满足另外一定条件时，将 i 指针右移，即 i = i.next。
当满足其他一定条件时，将 j 指针右移，即 j = j.next。
当其中一个链表遍历完时或者满足其他特殊条件时跳出循环体

代码模版

const i = head1, j = head2

while (i && j) {
    if (一定条件1) {
        i = i.next
        j = j.next
    } else if (一定条件2) {
        i = i.next
    } else {
		j = j.next
    }
}

适用范围

用于有序链表合并

21. 合并两个有序链表

链表环解法2——哈希表

链表环可以使用步长不一致的快慢指针解决，但是考虑的点会比较多，哈希表解决会容易一点，不过空间成本会更大

求解步骤

定义一个哈希表 set
不断遍历链表，判断当前节点是否在哈希表中存在了，如果存在做某些事情，如果不存在，则把节点加入到哈希表中

代码模版

const set = new Set<ListNode>()

while (head) {
	if (set.has(head)) {
        // ...do something
    } else {
        set.add(head)
    }
    head = head.next
}

141. 环形链表

var hasCycle = function(head) {
  const set = new Set()
  while (head) {
    if (set.has(head)) return true
    set.add(head)
    head = head.next
  }
  return false
};

142. 环形链表 II

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