[LeetCode] 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.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}

思路：

很经典的题，考到了链表的很多特性和技巧，要迅速写对写好不容易。大致思路分三步：
(1) 找到链表后一半。
(2) 将后一半节点反转。
(3) 将后一半节点依次插入前一半。

解法实现时有不少要注意的地方：

I. 奇偶链表长度：

偶数长度：1->2->3->4

(1) 1->2->3<-4

      |                |

      h1             h2

(2) 1->4->2->3

                 |     |

                 h1  h2 

奇数长度：1->2->3->4->5

(1) 1->2->3<-4<-5

      |                      |

      h1                   h2

(2) 1->5->2->3<-4

                 |           |

                 h1        h2

(3) 1->5->2->4->3

                             |

                            h1, h2

规律：如果链表长度为L，无论L是奇数还是偶数，都从第k = L/2+1 个节点起反转。

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

可以扫描两遍，第一遍得到L，并计算k。而第二遍扫描找到节点k。而更好的方法则是采用快慢双指针的策略：f每次走两步，s每次走一步。当f到达最后一个节点(而不是NULL)时，s指向k。同样分奇偶长度来验证：

偶数长度：1->2->3->4

(1) 1->2->3->4->NULL

            |     |

            s    f

(2) 1->2->3->4->NULL

                  |     |

                  s    f

奇数长度：1->2->3->4->5

(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; } };