## Thursday, November 20, 2014

### [LeetCode] Reorder List

Given a singly linked list LL0L1→…→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}`

(1) 找到链表后一半。
(2) 将后一半节点反转。
(3) 将后一半节点依次插入前一半。

I. 奇偶链表长度：

(1) 1->2->3<-4
|                |
h1             h2

(2) 1->4->2->3
|     |
h1  h2

(1) 1->2->3<-4<-5
|                      |
h1                   h2

(2) 1->5->2->3<-4
|           |
h1        h2

(3) 1->5->2->4->3
|
h1, h2

II  如何找到第k=L/2+1个节点？

(1) 1->2->3->4->NULL
|     |
s    f

(2) 1->2->3->4->NULL
|     |
s    f

(1) 1->2->3->4->5->NULL
|     |
s    f

(2) 1->2->3->4->5->NULL
|          |
s         f

III 如何将后一半反转的链表节点依次插入前一半中？

(1) 用双指针left/right分别从左右两头开始向中间扫描。依次将right所指节点插入left节点后面。每次插入后，left需要移动两次。

(2) 终止条件：当right扫描到最后一个节点(left->next==NULL)时结束，而该节点就是原链表中的第k=L/2+1个节点。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40``` ```class Solution { public: void reorderList(ListNode *head) { ListNode *mid = findMid(head); ListNode *right = reverseList(mid); ListNode *left = head; while(right && right->next) { ListNode *target = right; right = right->next; target->next = left->next; left->next = target; left = left->next->next; } } ListNode *findMid(ListNode *head) { ListNode *fast = head; ListNode *slow = head; while(fast && fast->next) { fast = fast->next; if(fast->next) fast = fast->next; slow = slow->next; } return slow; } ListNode *reverseList(ListNode *head) { if(!head) return head; ListNode *pre = head, *cur = head->next; while(cur) { ListNode *temp = cur->next; cur->next = pre; pre = cur; cur = temp; } head->next = NULL; return pre; } }; ```