Reorder List解题报告

Description:

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.

Example:

Given {1,2,3,4}, reorder it to {1,4,2,3}.

Link:

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

解题方法：

1. 找到中点将List分为两部分
2. 将后半部分逆置
3. 将后半部分插入到前半部分

Tips:

在这里求中点的方法与其他题目有一点不同，我们需要保证在node（假设node编号从1~2n）的个数为偶数的情况下求到第n个，而不是第n+1个：

while(fast && fast->next && fast->next->next)
{
            fast = fast->next->next;
            slow = slow->next;
}

Time Complexity：

O(N)时间
O(0)空间

完整代码：

void reorderList(ListNode* head) 
{
        if(!head)
            return;
        //get the start node of second part
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* second = slow->next;
        slow->next = NULL;
        //reverse second part
        ListNode* prev = NULL;
        ListNode* curr = second;
        while(curr)
        {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        second = prev;
        //build new list
        ListNode* first = head;
        while(second)
        {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;
            first->next = second;
            second->next = temp1;
            first = temp1;
            second = temp2;
        }
}