2023-07-31力扣每日一题

链接：

143. 重排链表

题意：

将链表L0 → L1 → … → Ln - 1 → Ln变成L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

解：

线性表法还是好写的

这边搞一下翻转法，快慢指针求翻转点（翻转后面一半然后双指针合并成一个）

还是喜欢递归翻转或者新头结点翻转QWQ，不过还是写了一下循环直接翻转

找到翻转点（不包含在翻转后的链表里）之后先将记录TA的下一个然后TA->next=nullptr，将指针TA转到记录上，然后再记录TA的下一个，再将现在TA的next设成nullptr，断开两部分链表

在这里插入图片描述

两个需要特判的地方，翻转点后面是nullptr则没有需要翻转的，翻转点后面的后面没有点则不需要进入循环（即不存在下一个<-代码注释）

然后每次记录处理节点的下一个N和下下一个NN，将下一个的next指向自身（翻转）(下一个代表节点，next代表指针)

这时候由于TA下一个的next指向TA，所以当TA移动到下一个以后，不能通过再访问next获取正确的下一个，所以要用nextnext来更新next，然后nextnext与后面还保持正确的顺序，用nextnext的next来更新nextnext

~~比较麻烦，感觉不如递归~~ 总之就是先记录原顺序再进行翻转操作，就是很注意越界条件

在这里插入图片描述

实际代码：

#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
void add(ListNode* &temp,ListNode* &addor) 
{
    if(temp==nullptr) temp=addor;
    else
    {
        temp->next=addor;
        temp=temp->next;
    }
}
/*
void reorderList(ListNode* head)//线性表 
{
    ListNode* temp=head;
    vector<ListNode*>lists;
    while(temp!=nullptr)
    {
        lists.push_back(temp);
        temp=temp->next;
    }
    int lg=lists.size();
    int l=0,r=lg-1;temp=nullptr;
    for(;l<=r;l++,r--)
    {
        add(temp,lists[l]);
        if(l!=r) add(temp,lists[r]);
    }
    temp->next=nullptr;
}*/
void Build(ListNode* &Reverse,ListNode* temp)
{
    ListNode* next=temp->next,*nextnext;temp->next=nullptr;//前面断开后面
    temp=next;//截断前面不需要翻转的 
    if(temp->next!=nullptr)//存在下一个 
    {
        next=temp->next;//记录下一个 
        nextnext=next->next;//记录正确的下下个（可能是空）
    }
    else next=nullptr;
    temp->next=nullptr;//翻转后作为尾结点要指向空 //后面断开前面 完成断开 
    while(next!=nullptr)
    {
        next->next=temp;//下一个指向自己 
        temp=next;//自己变成下一个 
        next=nextnext;//现在的下一个变成之前记录的正确目标 
        if(next!=nullptr) nextnext=next->next;//记录正确的下下个
        else break;
    }
    Reverse=temp;
}
void reorderList(ListNode* head)//翻转 
{
    ListNode *slow=head,*fast=head;
    while(slow!=nullptr&&fast!=nullptr)
    {
        fast=fast->next;
        if(fast!=nullptr) fast=fast->next;
        else break;
        slow=slow->next;
    }
    cout<<slow->val<<endl;//翻转点 
    ListNode *Reverse=nullptr;
    if(slow->next!=nullptr) Build(Reverse,slow);//构建 
    slow=head,fast=Reverse;
    while(slow!=nullptr&&fast!=nullptr)
    {
        ListNode *snext=slow->next,*fnext=fast->next;
        slow->next=fast;
        fast->next=snext;
        slow=snext;
        fast=fnext;
    }
}
int main()
{
    ListNode* head=nullptr;
    int n;cin>>n;
    ListNode* now=nullptr;
    for(int i=1;i<=n;i++)
    {
        //int temp;cin>>temp;
        if(head==nullptr)
        {
            head=new ListNode(i);
            now=head;
        }
        else
        {
            now->next=new ListNode(i);
            now=now->next;
        }
    }
    reorderList(head);
}

限制：