LeetCode毎日1題:merge k sorted list
1103 ワード
問題の説明
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
もんだいぶんせき
以前に書いた2つの秩序チェーンテーブルmergeTwoLists()関数を用いて,k回ループすればよいが,複雑度はO(n*k)=O(n^2)である.
コード実装
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
もんだいぶんせき
以前に書いた2つの秩序チェーンテーブルmergeTwoLists()関数を用いて,k回ループすればよいが,複雑度はO(n*k)=O(n^2)である.
コード実装
public ListNode mergeKLists(ArrayList lists) {
if (lists.size() == 0) return null;
ListNode head = lists.get(0);
for (int i = 1; i < lists.size(); i++) {
head = mergeTwoLists(head, lists.get(i));
}
return head;
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 == null) {
cur.next = l2;
}
if (l2 == null) {
cur.next = l1;
}
return head.next;
}