## Saturday, November 23, 2013

### [LeetCode] Reorder List, Solution

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}`.

[Thoughts]

1. 找出中间节点

2. 把中间节点之后的后半部分链表反序

3. 把前半部分链表及后半部分链表合并

[Code]

` 1     void reorderList(ListNode *head) { 2         if(head == NULL) return; 3         // find the median node 4         ListNode* fast = head; 5         ListNode* slow = head; 6         while(true) 7         { 8             fast = fast->next; 9             if(fast == NULL)10                 break;11             fast = fast->next;12             if(fast == NULL)13                 break;14             slow = slow->next;15         }16         17         if(slow == NULL) return;18         19         // reverse second half of link list20         ListNode* cur = slow;21         ListNode* pre = slow->next;22         cur->next = NULL;23         while(pre!=NULL)24         {25             ListNode* temp = pre->next;26             pre->next = cur;27             cur = pre;28             pre = temp;29         }30         31         // merge two lists32         ListNode* first = head;33         ListNode* second = cur;34         35         while(second!= NULL&& first!=NULL && first!=second)36         {37             ListNode* temp = second->next;38             second->next = first->next;39             first->next = second;40             first = second->next;41             second = temp;42         }43     }`