✉️문제
https://leetcode.com/problems/merge-k-sorted-lists/description/
Merge k Sorted Lists - LeetCode
Can you solve this real interview question? Merge k Sorted Lists - You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: Input: lis
leetcode.com
🗝 문제풀이
1. Collection과 Collection.sort를 이용한 풀이
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<ListNode> nodes = new ArrayList<>();
for(ListNode node : lists) {
while(node != null) {
nodes.add(node);
node = node.next;
}
}
Collections.sort(nodes, (a, b) -> a.val - b.val);
ListNode root = new ListNode();
ListNode prev = root;
for(ListNode n : nodes) {
root.next = n;
root = n;
}
return prev.next;
}
}
2. 합병정렬을 이용한 풀이
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return mergeHelper(lists, 0, lists.length - 1);
}
public ListNode mergeHelper(ListNode[] lists, int start, int end) {
if(start == end) return lists[start];
int mid = (start + end) / 2;
ListNode left = mergeHelper(lists, start, mid);
ListNode right = mergeHelper(lists, mid + 1, end);
return merge(left, right);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode tmp = new ListNode();
ListNode ans = tmp;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
tmp.next = l1;
l1 = l1.next;
} else {
tmp.next = l2;
l2 = l2.next;
}
tmp = tmp.next;
}
tmp.next = l1 == null ? l2 : l1;
return ans.next;
}
}