[LeetCode # 23 ~ 24] 문제 풀이

# 23. Merge k Sorted Lists

k 개의 정렬된 리스트가 주어질 때, 하나의 리스트로 이를 합치는 문제

 

리스트 별로 Pointer 를 놓고, 그 중 값이 제일 작은 노드를 찾아서 이를 연결해도 문제를 풀 수 있지만 이렇게 할 경우 k 가 커지면 하나하나 비교하는 게 시간이 오래 걸릴 것 같았다.

그래서 Counting Sort 의 방식을 사용해서, 모든 노드들이 갖는 값을 찾고 각각의 값들이 등장한 회수를 저장한 다음 그 횟수만큼 리스트에 추가하도록 구현했다.

 

int cnt[20001];

ListNode* mergeKLists(vector<ListNode*>& lists) {
	int total_cnt = 0;
	for (auto list : lists) {
		for (ListNode* tmp = list; tmp != nullptr; tmp = tmp->next) {
			cnt[tmp->val + 10000]++;
			total_cnt++;
		}
	}

	ListNode *dummy = new ListNode(0);
	ListNode *cur = dummy;

	for (int i = 0; i < 20001; i++) {
		if (total_cnt == 0)
			break;
		while (cnt[i]--) {
			cur->next = new ListNode(i - 10000);
			cur = cur->next;
			total_cnt--;
		}
	}
	return dummy->next;
}

# 24. Swap Nodes in Pairs

리스트가 주어졌을 때, 각각 인접한 노드들끼리 저장된 값을 Swap 하는 문제

 

단순히 리스트를 순차 탐색하면서 두 노드마다 한 번씩 앞뒤로 값을 바꿔주도록 만들었다.

 

void swap(ListNode* l1, ListNode* l2) {
	int tmp = l1->val;
	l1->val = l2->val;
	l2->val = tmp;
}

ListNode* swapPairs(ListNode* head) {
	bool flag = true;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		if (flag && tmp->next != nullptr) {
			swap(tmp, tmp->next);
		}
		flag = !flag;
	}
	return head;
}