题解 | #重排链表# C++O(1)空间 递归写法

思路其实挺简单的.

我们需要将头结点率先链接至尾节点.并且为了可持续性地将tail = tail -> pre.

在O(1)空间的情况下,使用递归是最好的选择.

使用一个全局变量保存为当前链的起始头部.而递归则是最先处理最尾部的节点

//这里我们只考虑最后一个节点5,是如何被放入头结点的.
/*
 此时的状态:
 		root->{1,2,3,4,5}
        tmp->{2,3,4,5}
        now->{4,5}
*/
root->next = now->next
/*
 此时的状态:
 		root->{1,5}
        tmp->{2,3,4,5}
        now->{4,5}
*/
root->next->next = tmp
/*
 此时的状态:
 		root->{1,5,2,3,4,5,2,3,4,5,2,3,4,5,...}
        tmp->{2,3,4,5,2,3,4,5,2,3,4,5,...}
        now->{4,5,2,3,4,5,2,3,4,5,...}
//可见,不将4,5断开后患无穷.
*/
now->next = nullptr;
/*
 此时的状态:
 		root->{1,5,2,3,4}
        tmp->{2,3,4}
        now->{4}
*/
root = tmp;
/*
此时的状态:
 		root->{2,3,4}
        tmp->{2,3,4}
        now->{4}
那么下一次运行时最尾端的节点就是 4,起始点就是2了
*/
//

class Solution {
public:
    ListNode* root;
    int len=0;
    void dfs(ListNode *now,int pos)
    {
        //用于记录总长度.
        len++;
        if(now->next==nullptr)return;
        //先让程序跑到最终点
        dfs(now->next,pos+2);
        //如果现在属于链表的前一半则不需要交换
        if(pos<len)return;
        auto tmp = root->next;
        root->next=now->next;
        root->next->next=tmp;
        now->next = nullptr;
        root=tmp;
    }
    
    void reorderList(ListNode *head) {
        if(head==nullptr)return ;
        root = head;
        dfs(head,1);
    }
};