[LeetCode] 86. Partition List

轉自LeetCode

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

<Solution>

這題再多看一個例子，given 3->1 and x = 2，則答案會是 1->3

也就是不管 x 在不在 list 裡，比 x 小的都在前面，大於等於 x 的都在後面

且原本的順序要維持住

解題想法如下

• 分兩個 linked list 來存，一個存比 x 小的 node，一個存大於等於 x 的 node

• 最後再將兩者合併

舉例:

7 -> 3 -> 8 -> 4 -> 1 -> 2，x = 4

round 1: 

list   : 3 -> 8 -> 4 -> 1 -> 2

list 1 :

list 2 : 7

round 2: 

list   : 8 -> 4 -> 1 -> 2

list 1 : 3

list 2 : 7

round 3: 

list   : 4 -> 1 -> 2

list 1 : 3

list 2 : 7 -> 8

round 4: 

list   : 1 -> 2

list 1 : 3

list 2 : 7 -> 8 -> 4

round 5: 

list   : 2

list 1 : 3 -> 1

list 2 : 7 -> 8 -> 4

round 6: 

list   :

list 1 : 3 -> 1 -> 2

list 2 : 7 -> 8 -> 4

combine:

3 -> 1 -> 2 -> 7 -> 8 -> 4

code 如下

	/**
	* 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 *dummy_1 = new ListNode(0);
	ListNode *dummy_2 = new ListNode(0);
	ListNode *pNode_1 = dummy_1, *pNode_2 = dummy_2;
	//> divided into two linked lists
	//> one is smaller than x
	//> one is equal or bigger than x
	while(head) {
	if(head->val < x) {
	pNode_1->next = head;
	pNode_1 = pNode_1->next;
	}
	else {
	pNode_2->next = head;
	pNode_2 = pNode_2->next;
	}
	head = head->next;
	}
	//> combine
	pNode_2->next = NULL;
	pNode_1->next = dummy_2->next;
	return dummy_1->next;
	}
	};

view raw partitionList.cpp hosted with ❤ by GitHub