<Hard> Merge k Sorted Lists (LeetCode : C#)

https://leetcode.com/problems/merge-k-sorted-lists/

📕 문제 설명

오름차순으로 정렬된 k개의 연결리스트가 담긴 배열이 주어질 때 하나의 연결 리스트로 합친 후 정렬해서 반환

• Input
  k개의 연결리스트가 담긴 배열
• Output
  하나로 합친 후 정렬된 연결 리스트

예제

풀이

1. 각 리스트노드별로 모두 순회하며 딕셔너리에 <해당 값, 개수>로 저장한다.
2. 딕셔너리 Key값을 기준으로 정렬한 리스트를 만든다.
3. Key로 딕셔너리 value 값 (즉, 개수)만큼 반복하며 해당 Key를 val값으로 해서 연결 리스트를 만든다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
    	// 값, 개수
        Dictionary<int, int> numDict = new Dictionary<int, int>();
        for(int i = 0; i < lists.Length; i++)
        {
            ListNode curr = lists[i];
            while(curr != null)
            {
                if (numDict.TryGetValue(curr.val, out int value))
                {
                    numDict[curr.val] += 1; // 존재하면 개수 증가
                }
                else
                {
                    numDict[curr.val] = 1; // 존재 안하면 count 1로 생성
                }
                curr = curr.next;
            }
        }

        List<int> numList = numDict.Keys.ToList();
        numList.Sort(); // key 정렬

        ListNode currNode = new ListNode(0);
        ListNode answerNode = currNode;

        foreach(int num in numList)
        {
            for (int i = 0; i < numDict[num]; i++) // 개수만큼 값 연결
            {
                currNode.next = new ListNode(num);
                currNode = currNode.next;
            }
        }

        return answerNode.next;

    }
}

결과