時間限制：1秒 空間限制：32768K
題目描述
Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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) {
if(head==nullptr || head->next==nullptr)
return;
ListNode* fast=head;
ListNode* slow=head;
while(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
}
ListNode* after=slow->next;
slow->next=nullptr;//斷開兩個鏈表
ListNode* pre=nullptr;
while(after){
//倒序后一個鏈表
ListNode* next=after->next;
after->next=pre;
pre=after;
after=next;
}
slow=head;
while(slow&&pre){
//合并兩個鏈表
ListNode* next=slow->next;
ListNode* preNext=pre->next;
pre->next=next;
slow->next=pre;
slow=next;
pre=preNext;
}
}
};
運行時間：23ms
占用內(nèi)存：1788k
