Leetcode 重排链表 递归

https://leetcode.com/problems/reorder-list/solutions/45113/Share-a-consise-recursive-solution-in-C++/

https://leetcode.cn/problems/reorder-list/solutions/32910/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-34/

列表的核心就是随机访问，无法得到任意位置的节点

1->2->3->...->n-2->n-1->n->#

1->n->2->n-1->3->...->(odd: (n+1)/2,even: n/2->n/2+1)->#

比如

• 1->2->3->4->5->6->#
• 1->6->f(2->3->4->5->#)

注意不是 1->f(2->3->4->5->6->#)

• 1->6->2->5->f(3->4->#)
• 1->6->2->5->3->4>#

因此这里存在子结构

但是递归基怎么写呢

• 1->6->f(2->3->4->5->#)
• 1->6->f(2->3->4->5->#) = 1->g(1->next) = 1->g(6->2->5->3->4>#)

我们只有一个head，比如说1

f(1) = 1->g(1->next) = 1->g(2) = 1->6->f(2)

f(head) = head->g(head->next)
g(head) = tail(head)->f(head->next)
f(head) = head->tail(head->next)->f(head->next->next)

问题在于此！tail无法实现