[LeedCode OJ]#86 Partition List

[LeedCode OJ]#86 Partition List

題意：

給定一個鏈表和一個x，要求在不改變其在原本鏈表中相對位置的情況下，將小於x的結點放在新鏈表的左邊，大於等於x的結點放在新鏈表的右邊

思路：

思路很簡單，新建兩個鏈表，一個存放大於等於x的結點，一個存放小於x的結點，左後再合並兩個鏈表即可。

/**
 * 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)
		{
			if(head==nullptr) return nullptr;
			ListNode *big = new ListNode(0);
			ListNode *small = new ListNode(0);
			ListNode *pa = big;
			ListNode *pb = small;
			ListNode *cur = head;
			while(cur)
			{
				ListNode *pnext = cur->next;
				if(cur->val>=x)
				{
					pa->next = cur;
					pa = pa->next;
					pa->next = nullptr;
				}
				if(cur->valnext = cur;
					pb = pb->next;
					pb->next = nullptr;
				}
				cur = pnext;
			}
			pb->next = big->next;
			return small->next;
		}
};