链接:
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