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);
}

限制：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000