# single linked list 정렬하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

#include <iostream> /* 참고문서 1. https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC */ struct ListNode { int val; ListNode* next; ListNode(int x, ListNode* next) : val(x), next(next) {} }; ListNode* Solution(ListNode* head); void main() { ListNode* head; head = new ListNode(7, nullptr); head = new ListNode(3, head); head = new ListNode(9, head); head = new ListNode(9, head); head = new ListNode(2, head); head = new ListNode(1, head); head = new ListNode(1, head); head = Solution(head); } ListNode* Solution(ListNode* head) { if (head == nullptr) { std::cout << " head pointer is nullptr, retry again." << std::endl; return nullptr; } ListNode* curUnsortedNode = head; ListNode* headOfSortedList = new ListNode(curUnsortedNode->val, nullptr); while (curUnsortedNode->next != nullptr) { curUnsortedNode = curUnsortedNode->next; ListNode* tmpNode = headOfSortedList; headOfSortedList = new ListNode(curUnsortedNode->val, tmpNode); ListNode* curSortedNode = headOfSortedList; ListNode* traverseNode = headOfSortedList->next; ListNode* prevSortedNode = nullptr; bool isFindPos = false; //finding position for insert data while (traverseNode != nullptr) { if (curSortedNode->val < traverseNode->val) { break; }else if (curSortedNode->val >= traverseNode->val) { prevSortedNode = traverseNode; isFindPos = true; } traverseNode = traverseNode->next; } // Not find position, continue.. if (isFindPos == false) continue; //insertion data ListNode* anotherNodes = traverseNode; ListNode* changeNode = curSortedNode; ListNode* newHead = curSortedNode->next; prevSortedNode->next = changeNode; changeNode->next = anotherNodes; headOfSortedList = newHead; } // release unsorted list. ListNode* originList = head; while (originList != nullptr) { ListNode* deleteNode = originList; originList = originList->next; delete deleteNode; } // clear unsortList pointer. curUnsortedNode = nullptr; return headOfSortedList; }