题目链接：

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

分析：

注意这里寻找中间节点的时候需要增加一个哑巴节点，否则1->2这种就会出错，具体代码如下：

class Solution {public:    ListNode* sortList(ListNode* head) {        if(head == NULL || head->next == NULL)        {            return head;        }        ListNode dummy(-1);        dummy.next = head;        ListNode *slow = &dummy;        ListNode *fast = &dummy;        while(fast != NULL && fast->next != NULL)        {            slow = slow->next;            fast = fast->next->next;        }        ListNode *p1 = head;        ListNode *p2 = slow->next;        slow->next = NULL;        ListNode *pp1 = sortList(p1);        ListNode *pp2 = sortList(p2);        return mergeList(pp1, pp2);    }private:    ListNode *mergeList(ListNode *p1, ListNode *p2)    {        if(p1 == NULL && p2 == NULL)        {            return NULL;        }        else if(p1 == NULL)        {            return p2;        }        else if(p2 == NULL)        {            return p1;        }        else        {            ListNode dummy(-1);            ListNode *cur = &dummy;            while(p1 != NULL && p2 != NULL)            {                if(p1->val < p2->val)                {                    cur->next = p1;                    p1 = p1->next;                }                else                {                    cur->next = p2;                    p2 = p2->next;                }                cur = cur->next;            }            if(p1 != NULL)            {                cur->next = p1;            }            if(p2 != NULL)            {                cur->next = p2;            }            return dummy.next;        }    }};