Reorder List [leetcode] 这两种思路

第一个想法随着vector保存全部Node*

表拼接出来

    void reorderList(ListNode *head) {

        vector<ListNode*> content;

        ListNode * cur = head;

        while (cur)

        {

            content.push_back(cur);

            cur = cur->next;

        }

        int size = content.size();

        cur = NULL;

        for (int i = 0; i <= size - 1 - i; i++)

        {

            if (cur) cur->next = content[i];

            if (i != size - i - 1) content[i]->next = content[size - 1 - i];

            cur = content[size - 1 - i];

        }

        if (cur) cur->next = NULL;

    }

另外一种思路能够分成下面几个步骤：

1. 找到中间的节点nMid

2. 翻转nMid到末尾的链表

3. 拼接head和nMid

代码例如以下

    void reorderList(ListNode *head) {

        if (head == NULL) return;

        ListNode * mid = head;

        ListNode * endOfHead;

        ListNode * end = head;

        while (end)

        {

            end = end->next;

            endOfHead = mid;

            mid = mid->next;

            if (end)  end = end->next;

        }

        endOfHead->next = NULL;//end of first half

        //reverse

        if (mid == NULL) return;

        ListNode* p0, * p1, * p2;

        p1 = mid;

        p2 = mid->next;

		p1->next = NULL;

        while (p2)

        {

            p0 = p1;

            p1 = p2;

            p2 = p2->next;

            p1->next = p0;

        }

        mid = p1;

        //concat

        ListNode * newHead = head;

        while (mid && head)

        {

            head = head->next;

            newHead->next = mid;

            newHead = newHead->next;

            mid = mid->next;

            newHead->next = head;

            newHead = newHead->next;

        }

    }