首页 > 代码库 > [LeetCode] Reorder List 反向插入链表
[LeetCode] Reorder List 反向插入链表
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes‘ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
Hide Tags
Linked List 这题如果使用额外空间，挺容易实现的，确定了中间位置，然后后边的放入stack，然后从新构建链表。空间为O(n)。
如果不用额外空间，便使用栈空间，通过递归实现，这样逻辑比较复杂。
思路：
- 确定链表分开的点。
- 进入递归函数，递归到后半段的末尾。
- 递归函数返回钱构建链表。
这个很多细节，例如确定分开的点，如果node=4,
1 2 3 4 -> 1 4 2 3.
这样断开的位置其实是左起第三个，而node=5时，同样断开位置也是左起第三个，一步到位的方法是使用快慢索引，先快移1步，然后慢移一步，最后快移一步，这样不需要额外的变量。
while(1){ if(fast->next!=NULL) fast=fast->next; else break; slow=slow->next; if(fast->next!=NULL) fast=fast->next; else break; }
然后是递归函数，因为是单项链表，传递的变量有
void help_f(ListNode * &lft,ListNode * rgt)
前一个有引用，后一个没有，因为单项索引的约束，前半段需要不断后移，可以是同一个，这样省点空间，而后半段需要每次使用变量标记，所以不能够使用索引。
最终代码如下，时间非常的好26ms，排名统计中太前没有显示了：
#include <iostream>#include <queue>using namespace std;/** * Definition for singly-linked list. */struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {}};class Solution {public: void reorderList(ListNode *head) { if(head==NULL) return; ListNode *fast=head,*slow=head; while(1){ if(fast->next!=NULL) fast=fast->next; else break; slow=slow->next; if(fast->next!=NULL) fast=fast->next; else break; } ListNode * fnl_end=slow; fast=fnl_end; slow=head; help_f(slow,fast); fnl_end->next=NULL; return ; } void help_f(ListNode * &lft,ListNode * rgt) { if(rgt!=NULL) help_f(lft,rgt->next); else return ; rgt->next=lft->next; lft->next=rgt; lft=rgt->next; }};int main(){ ListNode n1(1),n2(2),n3(3),n4(4),n5(5); n1.next=&n2; n2.next=&n3; n3.next=&n4;// n4.next=&n5; Solution sol; sol.reorderList(&n1); ListNode *tmp = &n1; while(tmp!=NULL){ cout<<tmp->val<<endl; tmp=tmp->next; } return 0;}
[LeetCode] Reorder List 反向插入链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。