首页 > 代码库 > [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}.
/** * 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) { ListNode *p1=head,*p2=head,*pre; while(p2!=NULL && p2->next!=NULL)//找到后一半的开头节点head2； { pre = p1; p1 = p1->next; p2 = p2->next; p2 = p2->next; } if(p1 == p2) return; pre->next = NULL;//前一半的结尾标记 ListNode *head2 = p1; stack<ListNode*> st; while(head2) { st.push(head2); head2 = head2->next; } p1 = head; ListNode *ph1,*ph2; while(p1 && !st.empty() ) { ph1 = p1->next; ph2 = st.top(); st.pop(); p1->next = ph2; ph2->next = ph1; p1 = ph1; } if(!st.empty()) { ph1 = st.top(); ph1->next = NULL; st.pop(); ph2->next = ph1; } }};
（1）注意数据结构用stack比较方便，如果用遍历的方法，则会超时Time Limited Exceeded！
（2）测试用例中，head包括NULL,1个结点、2个结点、3个结点、4个结点，把这几个测试正确，其余的应该就没有问题了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。