You are given an array of k linked lists lists, where each linked list is sorted in ascending order.
Merge all the linked lists into one sorted linked list and return it.
Examples 1:
- Input: lists = [[1,4,5],[1,3,4],[2,6]]
- Output: [1,1,2,3,4,4,5,6]
- Explanation: The linked-lists are:
- [
- 1->4->5,
- 1->3->4,
- 2->6
- ]
- merging them into one sorted list:
- 1->1->2->3->4->4->5->6
Examples 2:
- Input: lists = []
- Output: []
Examples 3:
- Input: lists = [[]]
- Output: []
Constraints:
- k ==
lists.length - 0 <= k <= 10^4
- 0 <=
lists[i].length<= 500 - -10^4 <=
lists[i][j]<= 10^4 lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed 10^4.
---------------------------------------------------------------------------------------------------------
Solution in C#:
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
using System;
public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
if (lists == null || lists.Length == 0)
return null;
return MergeLists(lists, 0, lists.Length - 1);
}
private ListNode MergeLists(ListNode[] lists, int start, int end) {
if (start == end)
return lists[start];
int mid = (start + end) / 2;
ListNode left = MergeLists(lists, start, mid);
ListNode right = MergeLists(lists, mid + 1, end);
return MergeTwoLists(left, right);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null)
{
if (l1.val <= l2.val)
{
curr.next = l1;
l1 = l1.next;
}
else
{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if (l1 != null)
curr.next = l1;
else if (l2 != null)
curr.next = l2;
return dummy.next;
}
}
 |
The same question I saw in Amazon online assessment
ReplyDeletePython Solution [Bruteforce]
ReplyDelete# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
test = ListNode(0)
tail = test
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
elif list2:
tail.next = list2
return test.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
temp = [lists[0]]
for i in range(len(lists) - 1):
x = self.mergeTwoLists(temp[i], lists[i + 1])
temp.append(x)
return temp[-1]