[Java] LeetCode 23번 Merge k Sorted Lists

[Java] LeetCode 23번 Merge k Sorted Lists

k개의 정렬된 링크드 리스트를 1개의 정렬된 링크드 리스트로 합치는 문제이다. 머지소트와 상당히 흡사하다. 그래서 list의 길이가 2라면 두 리스트를 합쳐주고, 3이상이라면 반씩 쪼개어서 다시 merge 과정을 진행해준다.

class Solution { public ListNode mergeTwo(ListNode first, ListNode second) { ListNode ret = new ListNode(); ListNode cur = ret; while (first != null && second != null) { if (first.val < second.val) { cur.next = new ListNode(first.val); first = first.next; } else { cur.next = new ListNode(second.val); second = second.next; } cur = cur.next; } if (first != null) { cur.next = first; } else if (second != null) { cur.next = second; } return ret.next; } public ListNode mergeKLists(ListNode[] lists) { int n = lists.length; if (lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } else if (lists.length == 2) { return mergeTwo(lists[0], lists[1]); } else { ListNode[] left = new ListNode[n / 2]; ListNode[] right = new ListNode[(n + 1) / 2]; for (int i = 0; i < n / 2; i++) { left[i] = lists[i]; } for (int i = 0; i < (n + 1) / 2; i++) { right[i] = lists[i + n / 2]; } ListNode leftNode = mergeKLists(left); ListNode rightNode = mergeKLists(right); return mergeTwo(leftNode, rightNode); } } }

반응형

from http://blue-jay.tistory.com/79 by ccl(A) rewrite - 2021-09-29 05:27:56