第一次代碼：
class Solution {public: void reorderList(ListNode *head) { if(head == NULL || head->next == NULL) return ; ListNode* slow = head; ListNode* fast = head; do{ slow = slow->next; fast = fast->next->next; }while(fast != NULL && fast->next != NULL); //把整個(gè)鏈表劃分成2個(gè)等長(zhǎng)的子鏈表，如果原鏈表長(zhǎng)度為奇數(shù)，那么第一個(gè)子鏈表的長(zhǎng)度多1 ListNode* head1 = head; ListNode* head2 = slow->next; slow->next = NULL; ListNode* cur = head2; ListNode* next = cur->next; ListNode* PRev = NULL; while(cur != NULL){ next = cur->next; cur->next = prev; prev = cur; cur = next; } head2 = prev; ListNode* next2 = NULL; while(head2 != NULL){ next = head1->next; next2 = head2->next; head1->next = head2; head2->next = next; head1 = next; head2 = next2; } }};要注意在中斷點(diǎn)將兩部分都復(fù)制為NULL，否則可能會(huì)輸出太多內(nèi)容。
上面的代碼可讀性甚好，但是申請(qǐng)的變量有點(diǎn)多。下面優(yōu)化了一下，不過到底哪種風(fēng)格好，還是各有千秋吧。
class Solution {public: void reorderList(ListNode* head) { if(head == NULL || head->next == NULL) return ; ListNode* n1 = head; ListNode* n2 = head; do{ n1 = n1->next; n2 = n2->next->next; }while(n2 != NULL && n2->next != NULL); ListNode* n3 = n1->next; n1->next = NULL; n1 = NULL, n2 = n3; while(n2 != NULL){ n3 = n2->next; n2->next = n1; n1 = n2; n2 = n3; } ListNode* n4 = n1; n1 = head, n3 = n4; while(n3 != NULL){ n2 = n1->next; n4 = n3->next; n1->next = n3; n3->next = n2; n1 = n2; n3 = n4; } }};回過頭來重新做一遍，使用二級(jí)指針+deque：
class Solution {public: void reorderList(ListNode* head) { if(head == NULL) return ; ListNode** pp = &(head->next); ListNode* tmp = head->next; std::deque<ListNode*> deq; while(tmp != NULL){ deq.push_back(tmp); tmp = tmp->next; } bool even = true; while(!deq.empty()){ if(even){ tmp = deq.back(); deq.pop_back(); } else{ tmp = deq.front(); deq.pop_front(); } *pp = tmp; pp = &(tmp->next); tmp->next = NULL; even = !even; } }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
