首页 > 代码库 > [LeetCode]Reorder List
[LeetCode]Reorder List
题目：Reorder List
首尾重新结合形成新的链表；
要求：不能改变链表的元素，空间复杂度O(1)
题目意思：
将链表L0→L1→…→Ln-1→Ln重排变成L0→Ln→L1→Ln-1→L2→Ln-2→…
思路：
首先将链表分为前后两半；L0→L1→...→L(n+1)/2和L(n+1)/2 + 1→…→Ln-1→Ln
然后将后半段的链表逆置；Ln→Ln-1→…→L(n+1)/2 + 1
最后依次遍历两个链表将第二个（后半段）链表对应位置链接到第一个（前半段）的对应为置后面，这样拼接成新的链表。
如何逆置链表？
1.新建新的链表头，指向空指针；
2.从头开始遍历链表，按照如下顺序执行：
保存当前的下一个位置的节点，
将当前的下一个位置改为新链表的头部，
更新新链表的头部，使其指向当前链表，
更新当前指向的节点，使其指向前面保存的下一个位置；
3.循环执行上面的操作，知道链表为空，然后返回新链表的头指针。
L0→L1→L2→L3→L4→L5→L6→L7
新链表的头部为root = nullptr; p = head;head:L0.
循环的一次操作如下： 第一轮 第二轮 ...
ListNode* q = p->next;//保存下一个节点;q：L1 q：L2
p->next = root;//当前节点插入头部; p->next：nullptr p->next：L0
root = p;//更新头结点； root：L0 root：L1
p = q;//遍历后续节点 p：L1 p：L2
ListNode *LeetCode::reverseList(ListNode* head){ ListNode* root = nullptr;//逆置后的头结点 ListNode* p = head; while (p){ ListNode* q = p->next;//保存下一个节点 p->next = root;//当前节点插入头部 root = p;//更新头结点 p = q;//遍历后续节点 } return root; } void LeetCode::reorderList(ListNode* head){ if (!head || !head->next)return;//空链，或单节点 int count = 0;//记录链长 ListNode* p = head; while (p){//计算链长 p = p->next; ++count; } if(count % 2)count = (count + 1) / 2;//奇数时，链的后半段的位置 else count = count / 2; p = head; for (; count > 0; --count) {//找到后半段链的位置 if (count == 1){//将前半段链尾置空 ListNode* pre = p; p = p->next; pre->next = nullptr; break; } p = p->next; } ListNode* q = p; q = reverseList(q);//逆置后半段链表 p = head; while (q){//交替拼接前后半段链表 ListNode* r = p->next; p->next = q; q = q->next; p->next->next = r; p = r; } }
[LeetCode]Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。