23.08.15. 풀었던 문제들 복기

Leetcode 86. Partition List, 25분

 linked list에서 entry를 옮기는 방법을 알고 있으면 쉽게 풀리는 문제. 단, doubly linked list가 아니므로 head에 있는 값을 옮기기 위해 dummy head를 만들어야 했다.

 

접근 1.

 x보다 작은 것들만 옮기고, 기존 것들은 유지하는 방법. 

// Runtime 5 ms Beats 52.61% 
// Memory 10.3 MB Beats 21.22%

/*
x보다 작은 entry들은 다른 linked list로 옮기고, x보다 큰 entry들은 그대로 둠.
- start pointer를 하나 두고, x보다 작은 것은 다 start로 옮김. x 이상인 것은 순서를 유지한 채로 head에 있을 것임.

이후 start와 원래 head를 이어붙임.
*/

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

        // 제일 처음 것도 옮기기 위해 새로운 head temp를 둠
        ListNode* temp = new ListNode(101, head);
        head = temp;
        ListNode* cur = head->next, *prev = head;
        while(1){
            cur = prev->next;
            if(cur == NULL) break;
            if(cur->val < x){
                // 원래 것에서 뺌
                prev->next = cur->next;

                // 새로운 partition에 추가
                end->next = cur;
                cur->next = NULL;
                end = cur;
            }
            else{
                prev = prev->next;
                if(prev == NULL) break;
            }
        }
        head = temp->next;
        
        if(start->next == NULL) return head;
        start = start->next;
        end->next = head;
        return start;
    }
};

 

접근 2.

 x보다 작은 것들, x 이상인 것들을 각각의 linked list에 옮기고 두 linked list를 연결하는 방법.

// Runtime 8 ms Beats 38.42%
// Memory 10.2 MB Beats 48.14%

/*
x보다 작은 entry들은 less에 옮기고, x보다 큰 entry들은 ge에 옮김.
이수 less와 ge를 이어붙임.
*/

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less = new ListNode();
        ListNode* less_end = less;
        ListNode* ge = new ListNode();
        ListNode* ge_end = ge;

        while(head != NULL){
            if(head->val < x){ // less에 붙여넣음
                less_end->next = head;
                less_end = head;
            }
            else{
                ge_end->next = head;
                ge_end = head;
            }

            head = head->next;
        }

        // remove dummy & connect
        ge = ge->next;
        less_end->next = ge;
        less = less->next;
        ge_end->next = NULL;
        return less;
    }
};

 

시간복잡도

 linked list를 1번 순회하므로 O(n)

 

공간복잡도

 linked list 이외에 O(n) size의 공간은 사용하지 않는다. O(1)