今天刷链表。

206. 反转链表

迭代

很简单，保存cur.next，然后cur -> prev。

def reverseList(self, head: ListNode) -> ListNode:
    cur = head
    prev = None
    while cur:
        next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    return prev

递归

要用递归，先想子问题。比如我正序遍历的时候，对于每个节点，假设后面所有节点已经被反转了，然后进行操作即可。

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

注意本题有两个特殊情况：空链表和只有一个元素的链表。

画出转换之后的依赖链路，然后顺着该链路的顺序搭建新的链表。

def swapPairs(self, head: ListNode) -> ListNode:
    cur = head
    prev = None
    res = head if head else None
    while cur and cur.next:
        third = cur.next.next
        if prev:
            prev.next = cur.next
        else:
            res = cur.next
        cur.next.next = cur
        cur.next = third
        prev = cur
        cur = third
    return res

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

看到“倒数”，先快速撸了一个用栈的解法：

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    stack = []
    cur = head
    while cur:
        stack.append(cur)
        cur = cur.next
    next = None
    while n > 1:
        next = stack.pop()
        n -= 1
    cur = stack.pop()
    if cur == head:
        return next
    stack.pop().next = next
    return head

当然最好的解法还是快慢指针，我又用virtual head优化了一下：

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    vhead = ListNode()
    vhead.next = head
    left = vhead
    right = vhead
    while (n > 1):
        right = right.next
        n -= 1
    leftprev = vhead
    while right.next:
        leftprev = left
        left = left.next
        right = right.next
    leftprev.next = left.next
    return vhead.next

160. 相交链表

一遍过，很合理，因为吸取了上一题的经验。

我的双指针解法如下：扫两遍，第一遍让两个指针都停在链表的终点。如果相交，那么它们的终点应该是同一node。这次遍历还记录下两条链表的长度。第二遍让长的链表的指针多跑两条链表的差值，然后两个指针齐头并进走到相交的节点。

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    pa = headA
    pb = headB
    counta = 1
    countb = 1
    while pa and pa.next:
        counta += 1
        pa = pa.next
    while pb and pb.next:
        countb += 1
        pb = pb.next
    if pa != pb:
        return None

    if counta >= countb:
        for _ in range(counta - countb):
            headA = headA.next
    else:
        for _ in range(countb - counta):
            headB = headB.next
    while headA != headB:
        headA = headA.next
        headB = headB.next
    return headA

但是题解的方法更烧。和判断有环链表的快慢指针一样，找到不变量（这题中是a+b+c），无需增加限制，两个指针自然会走到一起。

142. 环形链表 II

这道题很棒，包含了链表双指针的很多知识。

  1. 恒等式：快指针走过的距离 = 慢指针走过的距离 * 2.
  2. 如果快指针追上并且超越了慢指针，它们必定在中间已经相遇过了，而不存在快指针”跳过“慢指针的情况。leetcode-master中有一个非常精彩的statement：fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
  3. 在环形链表中，慢指针在它的环中第一圈必然会与快指针相遇。想象慢指针与快指针在环入口同时出发，快指针需要追赶的距离为环的长度n。根据1中的恒等式，它们会在慢指针下一次经过环入口时相遇，此时慢指针走了一圈，快指针走了两圈。这还是最坏情况，其他情况中快指针已经在环的里面了，因此需要追赶的距离<n，会在慢指针没有走完第一圈时就相遇。

知道了这三个前提条件，再去看题解就能明白了。

总结

链表主要考察的是指针操作。

简单的链表题（比如反转链表），最好掌握迭代和递归两种方法。

复杂的链表题基本上要涉及双指针。双指针问题中一定要找出恒等条件。19是建立两个指针的恒等距离差；160是找到a+c+b=b+c+a；142是三个原则。