LeetCode OJ-- Reorder List **

https://oj.leetcode.com/problems/reorder-list/

将一个链表重新排序，比如 1 2 3 4 5，变成 1 5 2 4 3

1.找到中间节点 mid

2.将链表分成两部分 head,head2

3.将head2 逆序

4.将head head2，再合并成一个链表

class Solution {
public:
    void reorderList(ListNode *head) {
        //0 elements, 1 elements, 2 elements
        if(head == NULL || head != NULL && head->next == NULL || head!= NULL && head->next != NULL && head->next->next == NULL)
            return;
        
        //find middle
        ListNode *end = head;
        ListNode *mid = head;
        while(end)
        {
            end = end->next;
            if(end && end->next)
            {
                end = end->next;
                mid = mid->next;
            }
        }
        ListNode *head2 = mid->next;
        
        //split
        mid->next = NULL;
        
        //reverse head2
        ListNode *itr = head2;
        if(head2->next)
        {
            head2 = head2->next;
            itr->next = NULL;
            ListNode *tmp = NULL;
            while(head2)
            {
              tmp = head2;
              head2 = head2->next;
              tmp->next = itr;
              itr = tmp;
            }
            head2 = itr;
        }
        
        //union
        ListNode *dummy = new ListNode(1);
        ListNode *node1 = head;
        while(node1)
        {
            dummy->next = node1;
            node1 = node1->next;
            dummy = dummy->next;
            if(head2)
            {
                dummy->next = head2;
                head2 = head2->next;
                dummy = dummy->next;
            }
            else
                break;
        }
    }
};