LeetCode (C/C++) 86. Partition List

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

---

풀이

x를 기준으로 작은 값을 저장할 리스트(small)와 큰 값을 저장할 리스트(big)을 생성
주어진 리스트의 노드를 하나씩 탐색하며 x보다 작은 값이라면 small에, 큰 값이라면 big에 넣어 따로 저장 후 이를 합쳐 반환

---

코드

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode();
        ListNode* big = new ListNode();

        ListNode* result = small;
        ListNode* bigResult = big;
        ListNode* now = head;

        while (now) {
            if (now->val < x) {
                small->next = now;
                small = small->next; 
            }
            else {
                big->next = now;
                big = big->next; 
            }
            now = now->next;
        }
        small->next = bigResult->next;
        big->next = NULL;
        return result->next;
    }
};