Reorder List

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.

Have you met this question in a real interview? 

Yes

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

这题算是十八般武艺都用上了。。。

因为要reorder,所以要找到中间的位置，把中间以后的reverse,然后merge两个list...

算是linked list考察知识点比较全的了。。。

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: void */ void reorderList(ListNode *head) { // write your code here if (!head ||!head->next) return; ListNode* mid=find_middle(head); ListNode* tmp = reverse(mid->next); mid->next=0; merge(head, tmp); } ListNode* find_middle(ListNode* head){ if (!head || !head->next) return head; ListNode* slow=head; ListNode* fast=head->next; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } return slow; } ListNode* reverse(ListNode* head){ ListNode* prev=0; while(head){ ListNode* tmp=head->next; head->next=prev; prev=head; head=tmp; } return prev; } void merge(ListNode* a, ListNode* b){ ListNode dummy(0); ListNode* head=&dummy; while(a && b){ head->next=a; a=a->next; head=head->next; head->next=b; b=b->next; head=head->next; } if (a) head->next=a; if (b) head->next=b; } };