## Table of contents

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: 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
```

**Example 2:**

```
Input: lists = []
Output: []
```

**Example 3:**

```
Input: lists = [[]]
Output: []
```

**Constraints:**

`k == lists.length`

`0 <= k <= 10<sup>4</sup>`

`0 <= lists[i].length <= 500`

`-10<sup>4</sup> <= lists[i][j] <= 10<sup>4</sup>`

`lists[i]`

is sorted in**ascending order**.The sum of

`lists[i].length`

will not exceed`10<sup>4</sup>`

.

### Initial Approach

So looking at the question we have to sort and merge the 2D array(not an array but just thinking in this way) / Linked List

So first we make a empty linked list

We have to add all the values to the empty linked list as they are different LL just like a list in a 2D array

One thing we will use to iterate and add values while the other we will use to return the linked list as we have to return it from the start

So head.next will act as begin -> your LL

```
head=tmp= ListNode()
res=[]
for l in lists:
while l!=None:
res.append(l.val)
l=l.next
for val in sorted(res):
tmp.next=ListNode()
tmp=tmp.next
tmp.val=val
return head.next
```

### The above is the Code beats 78%

Time Complexity O(NlogN) as there is sorting :)

Space Complexity O(N)