[LinkedList][Medium] 143. Reorder List

Reorder List - LeetCode 

 

리스트가 주어질 때, 

리스트를 앞에서 하나, 뒤에서 하나 이런식으로 재정렬 하라.

 

우선 가운데 부분을 찾는다. 

이후 중간부터 버퍼에 넣고 뒤집는다. 

혹은 바로 list를 뒤집는다. 

이후에 하나씩 head에 넣으면서 순서를 바꾼다. 

 

void reorderList(ListNode* head) 
{
    // Find the center. 
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* prev = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        prev = slow;

        slow = slow->next;
        fast = fast->next->next;
    }
    if (prev != nullptr)
        prev->next = nullptr;

    if(slow != nullptr)
        cout << "center : " << slow->val << endl;

    // Reverse node from center to end. 
    ListNode* node = slow;
    prev = nullptr;
    while (node != nullptr)
    {
        ListNode* next = node->next;
        node->next = prev;

        prev = node;
        node = next;
    }

    if(prev != nullptr)
        cout << "r-head : " << prev->val << endl;

    if(prev == head)
        return;

    // Merge 2 list one by one. 
    node = head;
    ListNode* rnode = prev;

    prev = nullptr;
    ListNode* curNode = nullptr;
    bool front = true;
    while (node != nullptr || rnode != nullptr)
    {
        bool proc = false;
        if (front)
        {
            if(node != nullptr)
            {
                curNode = node;
                node = node->next;
                proc = true;
            }
        }

        if(!proc && rnode != nullptr)
        {
            curNode = rnode;
            rnode = rnode->next;
            proc = true;
        }

        if(prev != nullptr)
            prev->next = curNode;
        prev = curNode;
        front = !front;
    }
}

 

결과.