leetcode 148) Sort List

LV. Medium 🧐

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

Sort List - LeetCode

 

문제

Given the head of a linked list, return the list after sorting it in ascending order.

 

Example 1:

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

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is in the range [0, 5 * 10^4].
• -10^5 <= Node.val <= 10^5

 

문제 해결법

vector<int> num_list를 둬서 ListNode를 한번 돌면서 val 값을 다 저장한다.

num_list를 정렬하고 다시 ListNode를 한번 돌면서 val 값을 정렬된 수로 업데이트해준다.

시간 복잡도는 sort을 써서 nlogn이다.

 

해결 코드

class Solution {
public:
	ListNode* sortList(ListNode* head) {
		vector<int> num_list;
		ListNode *temp = head;

		while(temp) {
			num_list.push_back(temp->val);
			temp = temp->next;
		}
		sort(num_list.begin(), num_list.end());
		int i = 0;
		temp = head;

		while(temp) {
			temp->val = num_list[i++];
			temp = temp->next;
		}
		return head;
	}
};