Leetcode - 86. Partition List

문제

링크드 리스트와 값이 주어진다. 주어진 값 x를 기준으로 작은 값은 리스트의 왼쪽에 큰값은 그 뒤로 배치하라. 단 기존 리스트의 상대적인 순서는 유지되어야한다.

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

해결

x보다 작은값들의 리스트, x보다 같거나 큰 값들의 리스트 두개를 만들고 마지막에 합친다. 이를 위해 각각의 리스트에 head, tail를 가리키는 포인터가 필요.

두 개의 리스트를 만드는것까지는 금방했는데, 마지막에 합칠때 이런 저런 조건처리가 필요해 오래걸림.
총 3가지 경우의수를 처리해야함. 그리고 리스트가 비어있을 경우(이건 3으로 처리됨)
1. x값이 리스트의 모든 값보다 작은 경우
2. x값이 리스트의 모든 값보다 큰 경우
3. x값이 리스트 값 사이에 있는 경우

struct ListNode *partition(struct ListNode *head, int x){
    struct ListNode *l_head = NULL, *l_tail = head;
    struct ListNode *r_head = NULL, *r_tail = head;
    struct ListNode *node = head;
    
    for (;node != NULL; node = node->next) {
        if (node->val < x) {
            if (l_head == NULL) {
                l_head = node;
                l_tail = l_head;
            } else {
                l_tail->next = node;
                l_tail = node;
            }
        } else {
            if (r_head == NULL) {
                r_head = node;
                r_tail = node;
            } else {
                r_tail->next = node;
                r_tail = node;
            }
        }
    }
    /* x is less than all of nodes */
    if (l_head == NULL && r_head) {
        if (r_tail)
            r_tail->next = NULL;
        return r_head;
    }
    /* x is greater than all of nodes */
    if (r_head == NULL && l_head) {
        return l_head;
    }
    /* x is between the nodes */
    if (r_tail)
        r_tail->next = NULL;
    if (l_tail)
        l_tail->next = r_head;
    return l_head;
}