# 86-Partition List
###### tags: `Medium`
## Question
https://leetcode.com/problems/partition-list/
## Key
用兩個list承接比x大跟小的nodes，在遍尋head中node時，使用before跟after，最後要將兩個list連接使用afterNode，最後return時要回傳從頭開始的list，所以使用beforeNode

## Reference
## Solution

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* beforeNode = new ListNode(-1);
        ListNode* before = beforeNode;
        ListNode* afterNode = new ListNode(-1);
        ListNode* after = afterNode;
        
        while(head != NULL)
        {
            if(head->val < x)
            {
                before->next = head;
                before = before->next;
            }
            else
            {
                after->next = head;
                after = after->next;
            }
            head = head->next;
        }
        after->next = NULL;
        
        //connect two list
        before->next =  afterNode->next;
        return beforeNode->next; 
    }
};