首页 > 代码库 > Reorder List
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}.
思路:遍历输入链表,将每个元素存入数组中,然后分别向后、向前遍历数组,对链表进行交叉合并。
class Solution {public: void reorderList( ListNode *head ) { if( !head || !head->next ) { return; } vector<ListNode*> nodes; ListNode *curr = head; while( curr ) { nodes.push_back( curr ); curr = curr->next; } int begin = 0, end = (int)nodes.size()-1; while( begin+1 < end ) { nodes[end]->next = nodes[begin]->next; nodes[begin]->next = nodes[end]; ++begin; --end; } nodes[end]->next = 0; return; }};
上述方法使用了与链表元素总数等长的数组。为了满足常空间复杂度要求,参考网上的思路:从中间部分将输入链表分割为前后两个链表,然后将后一个链表翻转,最后交叉合并两个链表。
1 class Solution { 2 public: 3 void reorderList( ListNode *head ) { 4 if( !head || !head->next ) { return; } 5 ListNode *slow = head, *fast = head->next; 6 while( fast->next ) { 7 slow = slow->next; 8 fast = fast->next; 9 if( fast->next ) { fast = fast->next; }10 }11 fast = slow->next;12 slow->next = 0;13 fast = reverse( fast );14 slow = head;15 while( slow && fast ) {16 ListNode *tmp = slow->next;17 slow->next = fast;18 fast = fast->next;19 slow->next->next = tmp;20 slow = tmp;21 }22 return;23 }24 private:25 ListNode* reverse( ListNode *head ) {26 ListNode *next = head->next;27 head->next = 0;28 while( next ) {29 ListNode *tmp = next->next;30 next->next = head;31 head = next;32 next = tmp;33 }34 return head;35 }36 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。