思想

链表的数据结构基础是用额外的空间存储下一个数据的位置，以此换取不连续内存的存储，进而更高效的使用资源。
同时，链表在增删方面的时间复杂度是 O(1)。
在处理链表相关的问题时，解题重点是搞清楚关系的处理，当前节点和后续节点的关系，和之前节点的关系。在此基础上，往往使用递归的方式能够快速的解题。

实例

反转链表的一部分 leetcode 92

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

输入：
（1）head: ListNode，一个链表头结点；
（2）left: int，反转起始位置；
（3）right: int，反转结束位置。

输出：
ListNode，部分反转后的链表的头结点

举例：
当输入 head = [1,2,3,4,5]，left = 2，right = 4 时，反转链表 2 到 4 位置的元素，返回 [1,4,3,2,5]。

递归

递归的思路是思考反复执行的重复过程，并找到 base case。
任意部分的链表反转比较复杂，需要处理开头和结尾两个位置。先简化问题，处理反转前 N 个元素的链表反转问题：
上例先简化为 head = [2,3,4,5], n = 3，反转前三个链表元素，返回 [4,3,2,5]

2 -> 3 -> 4 -> 5 -> None

这个问题要识别当前元素的位置，因为只有前 n 个反转，后续不动。

2 -> reverse[null <- 3 <- 4] -> 5

reverse 是递归的部分，返回的结果如上描述，且返回了递归部分的头结点 4。
这时 2.next 指向的是 3，接下来的递归操作应该是

2.next.next = 2

将 2 的下一个节点指向 5，完成 reverse

2.next = 5

由此完成了递归的主体代码，接下来描述 base case 并要识别后续不需要反转的头结点。

if n == 1:
    # 这个例子进入 base 条件时，节点在 4，此时的非反转头结点就是 5
    successor = cur.next

reverse(head.next, n - 1)

当完成了简化问题的处理后，加入头部开始位置的递归判断。

if left != 1:
    # 如果当前节点不是反转的起始位置，则进入下一个节点，形成子链，此时子链的反转区间左右都减 1
    head.next = reverse(head.next, left - 1, right - 1)

编码

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    successor = None

    def reverseN(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if n == 1:
            self.successor = head.next
            return head
        last = self.reverseN(head.next, n - 1)
        head.next.next = head
        head.next = self.successor
        return last

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == 1:
            return self.reverseN(head, right)
        head.next = self.reverseBetween(head.next, left - 1, right - 1)
        return head

相关

链表 0