Reorder List

题目：

Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln

reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Example: Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

分析：

这道题目逻辑本身并不复杂，但是要不断的带入例子去检查奇偶性，一致性。

首先，在reverseList的时候，需要while(head->next != NULL)；其次，在findMiddle的时候要注意return slow，并且在后面例子用slow->next做newhead，这样做的好处是前一半的长度>=后一半的长度；最后，因为前一半更长，在while()循环中，需要保证有可能head没结束，但是newhead已经结束了，于是加入了if语句。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    ListNode* reverseList(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        while (head->next != NULL) {
            ListNode* next = head->next;
            head->next = next->next;
            next->next = dummy.next;
            dummy.next = next;
        }
        return dummy.next;
    } 

    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    void reorderList(ListNode *head) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return;
        }

        ListNode* mid = findMiddle(head);
        ListNode* newhead = mid->next;
        mid->next = NULL;
        newhead = reverseList(newhead);

        ListNode dummy(0);
        ListNode* curr = &dummy;

        while (head != NULL) {
            curr->next = head;
            head = head->next;
            curr = curr->next;

            if (newhead == NULL) {
                continue;
            }

            curr->next = newhead;
            newhead = newhead->next;
            curr = curr->next;
        }

    }
};