Partition List

링크드 리스트와 특정 정수 값이 주어진다.

해당 값을 기준으로 더 작은 값들과 같거나 큰 값들로 링크드 리스트를 분류해야 한다.

이미지 출처

분류 된 리스트 내의 순서는 기존의 링크드 리스트의 순서를 따라야 한다

/**
 * 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) {
        
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        
        ListNode* lessThan{nullptr};

        ListNode* greaterThanOrEqual{nullptr};
        ListNode* greaterThanOrEqualStart{nullptr};

        ListNode* now{head};
        ListNode* previous{head};
        
        while(now != nullptr)
        {
            previous = now;
            now = now->next;
            
            if (previous->val < x)
            {
                if (lessThan)
                {
                    lessThan->next = previous;
                    lessThan = previous;
                }
                else
                {
                    lessThan = previous;
                    head = previous;
                }
            }
            else
            {
                if (greaterThanOrEqual)
                {
                    greaterThanOrEqual->next = previous;
                    greaterThanOrEqual = previous;

                }
                else
                {
                    greaterThanOrEqual = previous;
                    greaterThanOrEqualStart = previous;
                }
            }
        }
        
        if (lessThan)
        {
            lessThan->next = greaterThanOrEqualStart;
        }
        else
        {
            head = greaterThanOrEqualStart;
        }
        
        if (greaterThanOrEqual)
        {
            greaterThanOrEqual->next = nullptr;
        }
        
        return head;
    }
};