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}.
s思路： 1. 這道題讓把list后半部分reverse后插入前半部分。 2. 做法也是先用快慢指針找到中點，然后把后半部分reverse，最后把reverse的后半部分一個一個的插入到前半部分。問題分成三步，每一步都很獨立，不需要交叉，和前面遇到的幾個步驟交叉進行的問題比，這個就是簡單的問題！
class Solution {public: void reorderList(ListNode* head) { //step 1：找中點！ if(!head) return; ListNode* fast=head->next,*slow=head; while(fast&&fast->next){//bug:用fast->next比用fast好 fast=fast->next?fast->next->next:NULL; slow=slow->next; } //step 2: reverse the right half ListNode* pnow=slow->next; while(pnow&&pnow->next){//千年bug:在不知道pnow是否有的情況下，不要直接寫pnow->next,需要加保護 //ListNode* pnext=pnow->next; ListNode* PRe=slow->next; slow->next=pnow->next; pnow->next=pnow->next->next; slow->next->next=pre; } //step 3:merge ListNode* l=head,*r=slow->next; slow->next=NULL;//關鍵位置：把左右兩部分斷開！ while(l&&r){ ListNode* p=l->next,*q=r->next; l->next=r; r->next=p; l=p; r=q; } }};新聞熱點
疑難解答
