思想
链表的数据结构基础是用额外的空间存储下一个数据的位置，以此换取不连续内存的存储，进而更高效的使用资源。
同时，链表在增删方面的时间复杂度是 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
