[Leetcode/C++] 147_Insertion Sort List

문제는 다음과 같습니다.

간단한 삽입정렬 문제입니다!

보자마자, 두 번의 for문을 돌리고, 내부의 for문은 항상 첫번째부터 첫번째의 for문이 도는 곳 이전까지 순회하면서 첫번째 for문이 가리키는 곳의 node의 위치를 찾으면 됩니다.

제 코드는 다음과 같습니다.

/**
 * 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* head) {
        for(auto cur = head->next; cur!=NULL; cur=cur->next){
            for(auto tmp = head; tmp!=cur; tmp=tmp->next){
                if(tmp->val > cur->val){
                    swap(cur->val, tmp->val);
                }
            }
        } // for문 끝
        return head;
    }
};