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/
解题方法：
- 找到中点将List分为两部分
- 将后半部分逆置
- 将后半部分插入到前半部分
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;
}
}
