23-moran991231.md

23. Merge k Sorted Lists

Solution 1

• 시간복잡도: O(N)

• 알고리즘 : 카운팅 정렬

• 풀이설명:

  • 입력: 연결 리스트들의 배열. 배열의 길이는 0500, 연결 리스트들의 길이는 010,000, 원소들의 값의 범위 -10,000~10,000 (입력 노드의 최대 개수는 5,000,000이다.)
  • 출력: 입력 배열에 들어있는 연결 리스트들을 모두 merge한 연결리스트
  • 원소들의 값의 범위는 -10000부터 10000까지로, 총 20001가지이다. 값의 범위가 작으니 카운팅 정렬을 사용하자.

  새로운 ListNode를 생성하지 않는다.

  입력배열(lists)의 연결리스트(lists[i])들을 하나씩 검사한다.

  연결리스트(lists[i])의 원소들을 앞에서부터 하나씩 검사하며 카운팅 배열인 nodes에 옮긴다.

  1. 연결리스트의 lists[i]의 head node를 pop하고 temp변수에 담는다. lists[i]의 새로운 head node는 temp.next와 같다.

  2. temp를 nodes[temp.val + 10000]에 push 한다. nodes[temp.val + 10000]의 새로운 head node는 temp와 같다.

  입력 연결리스트 배열의 원소가 모두 없어질 때까지1,2를 반복한다.

  3. 배열 nodes를 순차적으로 탐색하며 처음으로 null이 아닌 ListNode를 출력할 연결리스트의 head node로 삼는다.

  4. 배열 node를 이어서 탐색하며 null이 아니면 출력 연결리스트의 끝에 연결한다.

  • 예시)

    입력 lists = [[1,4,5],[1,3,4],[2,6]]

    카운팅 배열 nodes:[ ... [], ..., [1,1], [2], [3], [4,4], [5],[6], ..., [], ...] //[1,1]은 nodes의 10001번째 인덱스, []은 null

    병합된 연결리스트: [1,1,2,3,4,4,5,6]

  • 경계조건

    입력배열lists가 빈 배열이거나, lists의 원소 중에 빈 연결리스트가 있거나에 영향을 받지 않는다.

    다만 카운팅 배열에서 출력할 연결리스트의 head node를 찾는 //find head 끝 부분에서 temp변수에 연결리스트 head의 마지막 원소를 대입한다. head가 null일 경우 endOf(head)에서 node.next를 접근할 때 오류가 발생할 수 있으므로 if문을 사용하여 예외처리를 해준다.

​ 우선순위 큐를 사용한 풀이도 있다. 우선순위 큐 (heap)을 사용하면 시간복잡도가 O(N logN)이다.

• 소스코드

class Solution {
	
	public static ListNode endOf(ListNode node) {
		while (node.next != null) {
			node = node.next;
		}
		return node;
	}
    
	public static ListNode mergeKLists(ListNode[] lists) {
		int len = lists.length;
		ListNode head = null, temp=null;
		ListNode[] nodes = new ListNode[20_001];
        
        // counting...
		for (int i = 0; i < len; i++) {
			while (lists[i] != null) {
				temp = lists[i];
				lists[i] = temp.next; // pop head node in lists[i]
				temp.next = nodes[temp.val + 10000]; // push
				nodes[temp.val + 10000] = temp;
			}
		}

		// find head
		int start;
		for (start = 0; start < 20001; start++) {
			if (nodes[start] != null) {
				head = nodes[start];
				break;
			}
		}
		if (head != null) 
			temp = endOf(head);			
		 else temp = null;
        
		 //merge
		for(int i=start+1; i<20001; i++) {
			if (nodes[i]== null) continue;
			temp.next=nodes[i]; // concatenate
			temp = endOf(nodes[i]); // point to end of linked-list
		}

		return head;

	}
}

• 디버깅용 main함수

public class Test {
	
	static ListNode makeList(int[] nums) {
		if (nums.length==0) return null;
		ListNode head=null,temp;
		for(int i=nums.length-1; i>=0; i--) {
			temp = new ListNode(nums[i], head);
			head = temp;
		}
					
		return head;		
	}
	
	static void printList(ListNode head) {
		while(head != null) {
			System.out.printf("%d ", head.val);
			head = head.next;
		}
	}

	public static void main(String[] args) {
		ListNode[] lists = new ListNode[3];
		lists[0] = makeList(new int[]{1,4,5});
		lists[1] = makeList(new int[]{1,3,4});
		lists[2] = makeList(new int[]{2,6});
		
		ListNode ret = Solution.mergeKLists(lists);
		printList(ret);
	}

}