建网站需要服务器吗,做网站的软件工程师,商标设计网站免费,门户网站制作定做链接#xff1a;
143. 重排链表
题意#xff1a;
将链表L0 → L1 → … → Ln - 1 → Ln变成L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
解#xff1a;
线性表法还是好写的
这边搞一下翻转法#xff0c;快慢指针求翻转点#xff08;翻转后面一半然后双指针合并…链接
143. 重排链表
题意
将链表L0 → L1 → … → Ln - 1 → Ln变成L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
解
线性表法还是好写的
这边搞一下翻转法快慢指针求翻转点翻转后面一半然后双指针合并成一个
还是喜欢递归翻转或者新头结点翻转QWQ不过还是写了一下循环直接翻转
找到翻转点不包含在翻转后的链表里之后先将记录TA的下一个然后TA-nextnullptr将指针TA转到记录上然后再记录TA的下一个再将现在TA的next设成nullptr断开两部分链表 两个需要特判的地方翻转点后面是nullptr则没有需要翻转的翻转点后面的后面没有点则不需要进入循环即不存在下一个-代码注释
然后每次记录处理节点的下一个N和下下一个NN将下一个的next指向自身翻转(下一个代表节点next代表指针)
这时候由于TA下一个的next指向TA所以当TA移动到下一个以后不能通过再访问next获取正确的下一个所以要用nextnext来更新next然后nextnext与后面还保持正确的顺序用nextnext的next来更新nextnext
比较麻烦感觉不如递归 总之就是先记录原顺序再进行翻转操作就是很注意越界条件 实际代码
#includebits/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(tempnullptr) tempaddor;else{temp-nextaddor;temptemp-next;}
}
/*
void reorderList(ListNode* head)//线性表
{ListNode* temphead;vectorListNode*lists;while(temp!nullptr){lists.push_back(temp);temptemp-next;}int lglists.size();int l0,rlg-1;tempnullptr;for(;lr;l,r--){add(temp,lists[l]);if(l!r) add(temp,lists[r]);}temp-nextnullptr;
}*/
void Build(ListNode* Reverse,ListNode* temp)
{ListNode* nexttemp-next,*nextnext;temp-nextnullptr;//前面断开后面tempnext;//截断前面不需要翻转的 if(temp-next!nullptr)//存在下一个 {nexttemp-next;//记录下一个 nextnextnext-next;//记录正确的下下个可能是空}else nextnullptr;temp-nextnullptr;//翻转后作为尾结点要指向空 //后面断开前面 完成断开 while(next!nullptr){next-nexttemp;//下一个指向自己 tempnext;//自己变成下一个 nextnextnext;//现在的下一个变成之前记录的正确目标 if(next!nullptr) nextnextnext-next;//记录正确的下下个else break;}Reversetemp;
}
void reorderList(ListNode* head)//翻转
{ListNode *slowhead,*fasthead;while(slow!nullptrfast!nullptr){fastfast-next;if(fast!nullptr) fastfast-next;else break;slowslow-next;}coutslow-valendl;//翻转点 ListNode *Reversenullptr;if(slow-next!nullptr) Build(Reverse,slow);//构建 slowhead,fastReverse;while(slow!nullptrfast!nullptr){ListNode *snextslow-next,*fnextfast-next;slow-nextfast;fast-nextsnext;slowsnext;fastfnext;}
}
int main()
{ListNode* headnullptr;int n;cinn;ListNode* nownullptr;for(int i1;in;i){//int temp;cintemp;if(headnullptr){headnew ListNode(i);nowhead;}else{now-nextnew ListNode(i);nownow-next;}}reorderList(head);
}限制
链表的长度范围为 [1, 5 * 104]1 node.val 1000
