[LeetCode]Partition List

就是把一个linkedlist分解成两个linkedlist，我们各用两个指针分别track小于x的链表的头尾节点和大于等于x的链表的头尾节点即可。时间复杂度O(N)，常数空间，代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* partition(ListNode* head, int x) {
	ListNode* sHead = nullptr, *sCurr = nullptr, *gHead = nullptr, *gCurr = nullptr;
	auto curr = head;
	while(curr)
	{
	if(curr->val < x)
	{
	if(!sHead)
	{
	sHead = curr;
	sCurr = curr;
	}
	else
	{
	sCurr->next = curr;
	sCurr = sCurr->next;
	}
	}
	else
	{
	if(!gHead)
	{
	gHead = curr;
	gCurr = curr;
	}
	else
	{
	gCurr->next = curr;
	gCurr = gCurr->next;
	}
	}
	curr = curr->next;
	}
	if(sCurr)sCurr->next = gHead;
	if(gCurr)gCurr->next = nullptr;
	return sHead? sHead : gHead;
	}
	};

view raw Partition List.cpp hosted with ❤ by GitHub