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}.
解答： 這道題分三步，第一步找到中點，通過走一步和走兩步的方法找到鏈表中心。第二步，翻轉后面的鏈表。第三步，把兩個鏈表合起來。
/** * 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||!head->next) return; ListNode*p1=head,*p2=head->next;//這里得是p2=head->next,而非head,否則[1,2]這個testcase過不了 while(p2&&p2->next) { p1=p1->next; p2=p2->next->next; } ListNode *head2=p1->next; p1->next=NULL; p2=head2->next; head2->next=NULL; while(p2) { p1=p2->next; p2->next=head2; head2=p2; p2=p1; } p2=head2; p1=head; ListNode* t=p1->next; while(p2) { p1->next=p2; p1=p2; p2=t; t=p1->next; } }};新聞熱點
疑難解答
