LeetCode 147. Insertion Sort List

문제

https://leetcode.com/problems/insertion-sort-list/

걸린 시간

-

풀이

C++

/**
 * 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* insertionSortList(ListNode* h) {
        // empty list
        if(h == nullptr) return nullptr;
        // make root node
        ListNode* root = new ListNode(h->val);
        h = h->next;
        // linked list pointer
        ListNode* head = root;
        ListNode* tail = root;
        ListNode* cur = root;
        while(h != nullptr){
            // make new node
            int element = h->val;
            ListNode* node = makeNode(element);
            // search
            cur = head;
            while(cur->next != nullptr && element > cur->next->val) cur = cur->next;
            // insert
            if(cur == head){ // start
                if(element <= cur->val){
                    node->next = head;
                    head = node;
                }
                else{
                    if(cur == tail){
                        head->next = node;
                        tail = node;
                    }
                    else{
                        node->next = head->next;
                        head->next = node;
                    }
                }
            }
            else if(cur == tail){ // end
                cur->next = node;
                tail = node;
            }
            else{ // mid
                node->next = cur->next;
                cur->next = node;
            }
            h = h->next;
        }
        return head;
    }
    ListNode* makeNode(int val){
        ListNode* node = new ListNode(val);
        return node;
    }
};

단순한 삽입 정렬 문제인데 vector 내장 함수만 써 버릇 하다 링크드 리스트로 직접 구현하려다 보니 생각보다 많이 까다로웠다.