https://leetcode.com/problems/partition-list/

작은 값을 이어가는 list 하나, 크거나 같은 값작은 값을 이어가는 list 하나, 크거나 같은 값을 이어가는 list 하나 를 운행한다.

class Solution {
 public:
	 ListNode* partition(ListNode* head, int x) {
		 if (head == NULL || head->next == NULL) return head;
		 ListNode* smaller = new ListNode(-1);
		 ListNode* greater = new ListNode(-1);
		 ListNode* gDummy = greater;
		 ListNode* sDummy = smaller;
		 while (head)
		 {
			 if (head->val < x)
			 {
				 sDummy->next = head;
				 sDummy = sDummy->next;
			 }
			 else
			 {
				 gDummy->next = head;
				 gDummy = gDummy->next;
			 }
			 head = head->next;
		 }
		 gDummy->next = NULL;
		 sDummy->next = greater->next;

		 return smaller->next;
	 }
 };

Runtime: 8 ms, faster than 49.28% of C++ online submissions for Partition List.

Memory Usage: 10.1 MB, less than 99.53% of C++ online submissions for Partition List.