[LeetCode]Reorder List

要求in-place，所以不能用stack。解法分三个步骤：

• 分解，分成前半段和后半段两个链表
• 翻转，reverse第二个链表
• 合并，将两个链表merge起来

注意我们用fast.next ！= null && fast.next.next ！= null来判断分解的结束情况，因为这样可以让partition之后的链表前半部分等于后半部分，或者前半部分长度比后半部分少1，从而符合题目的要求。Merge的时候就相当于把第二个链表每隔一个node插入第一个链表当中，总的时间复杂度仍然是O(N)，常数空间。代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void reorderList(ListNode* head) {
	if(!head || !head->next)return;
	ListNode* fast = head, *slow = head;
	//partition
	while(fast->next && fast->next->next)
	{
	fast = fast->next->next;
	slow = slow->next;
	}
	auto head2 = slow->next;
	slow->next = nullptr;
	//reverse second
	head2 = reverse(head2);
	//merge second list into first list
	auto curr1 = head, curr2 = head2;
	while(curr2)
	{
	auto tmp = curr2->next;
	curr2->next = curr1->next;
	curr1->next = curr2;
	curr1 = curr1->next->next;
	curr2 = tmp;
	}
	}
	private:
	ListNode* reverse(ListNode* head)
	{
	ListNode* prev = head, *curr = head->next;
	prev->next = nullptr;
	while(curr)
	{
	auto tmp = curr->next;
	curr->next = prev;
	prev = curr;
	curr = tmp;
	}
	return prev;
	}
	};

view raw Reorder List.cpp hosted with ❤ by GitHub