[leetcode] 86. 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) {
        ListNode* ret = new ListNode();
        ListNode* dummy = ret;
        ListNode* bigger = new ListNode();
        ListNode* dummy2 = bigger;
        while(head){
            if(head->val < x){
                ListNode* tmp = new ListNode(head->val);
                ret->next = tmp;
                ret = ret->next;
            } else {
                ListNode* tmp = new ListNode(head->val);
                bigger->next = tmp;
                bigger = bigger->next;
            }
            head = head->next;
        }
        
        ret->next = dummy2->next;
        
        return dummy->next;
        
    }
};

 

리트코드에 데일리 챌린지라는게 있더군요,, 오늘 처음 풀어봤습니다.

다른 리스트 문제들과 비슷하게 접근하면 되고, 피벗값보다 크고 작은 경우를 나누어서 관리하면 간단하더군요.

90% 대의 결과가 나온걸로 봐서 거이 최적에 가까운 해일거 같습니다.

시간복잡도 : O(n)