Open azl397985856 opened 1 year ago
function mergeTwoLists(l1, l2) { const dummyHead = {}; let current = dummyHead; // l1: 1 -> 3 -> 5 // l2: 2 -> 4 -> 6 while (l1 !== null && l2 !== null) { if (l1.val < l2.val) { current.next = l1; // 把小的添加到结果链表 current = current.next; // 移动结果链表的指针 l1 = l1.next; // 移动小的那个链表的指针 } else { current.next = l2; current = current.next; l2 = l2.next; } }
if (l1 === null) { current.next = l2; } else { current.next = l1; } return dummyHead.next; }
先合并两个,两两合并最后再合到一起
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
# basic cases
if n == 0: return None
if n == 1: return lists[0]
if n == 2: return self.mergeTwoLists(lists[0], lists[1])
# divide and conqure if not basic cases
mid = n // 2
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
c1, c2, c3 = l1, l2, res
while c1 or c2:
if c1 and c2:
if c1.val < c2.val:
c3.next = ListNode(c1.val)
c1 = c1.next
else:
c3.next = ListNode(c2.val)
c2 = c2.next
c3 = c3.next
elif c1:
c3.next = c1
break
else:
c3.next = c2
break
return res.next
复杂度分析
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
if not lists:
return None
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged = mergeTwoLists(l1, l2)
merged_lists.append(merged)
lists = merged_lists
return lists[0]
def mergeTwoLists(l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
class Solution {
class Status implements Comparable<Status>{
int val;
ListNode ptr;
Status(int val, ListNode ptr){
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2){
return this.val - status2.val;
}
}
PriorityQueue<Status> queue = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {
for(ListNode node: lists){
if(node != null){
queue.offer(new Status(node.val, node));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while(!queue.isEmpty()){
Status f = queue.poll();
tail.next = f.ptr;
tail = tail.next;
if(f.ptr.next != null){
queue.offer(new Status(f.ptr.next.val, f.ptr.next));
}
}
return head.next;
}
}
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
if l1:
current.next = l1
if l2:
current.next = l2
return dummy.next
def mergeSortLists(lists, left, right):
if left == right:
return lists[left]
mid = left + (right - left) // 2
left_list = mergeSortLists(lists, left, mid)
right_list = mergeSortLists(lists, mid + 1, right)
return mergeTwoLists(left_list, right_list)
if not lists:
return None
return mergeSortLists(lists, 0, len(lists) - 1)
23. 合并 K 个排序链表
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/merge-k-sorted-lists/
前置知识
题目描述
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6