首页 > 代码库 > Reorder List

Reorder List

2024-07-16 22:24:42   225人阅读

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 };

 


联系
我们