Merge k Sorted Lists
Post
Cancel

# LeetCode #23: Merge k Sorted Lists (C/C++).

hard

source: https://leetcode.com/problems/merge-k-sorted-lists
C/C++ Solution to LeetCode problem 23. Merge k Sorted Lists.

## Problem

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.

## Examples

### 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 <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

## Solution

I propose 3 different solutions.

1. Using an auxiliary vector<int>
• Create a vector with all the elements.
• Sort the list.
• Create a linked list of ListNode elements from the values of the sorted vector.
2. Using hashmap (map<int, int> all)
• Add every val of the input lists (traking how many times the val appears).
• For every element in the map create as many nodes as necesary, adding them to the end of the linked list.
3. Sort nodes while reading them.
• The first list becomes out initial result.
• For every next list:
• For every node in list: we iterate throught the result list and once we find the place for the node we insert it there (reasigning the next pointers).

### Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* result = nullptr; vector<int> all; for (int l=0; l<lists.size(); l+=1) { ListNode* node = lists[l]; while(node) { all.push_back(node->val); node = (*node).next; } } sort( all.begin(), all.end(), [](int a, int b) { return a < b; } ); if (all.size()){ ListNode *tmp= new ListNode(all[0]); result = tmp; for (int n=1; n<all.size(); n+=1) { (*tmp).next = new ListNode(all[n]);; tmp = (*tmp).next; } } return result; } }; 

### Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* result = nullptr; map<int, int> all; for (int l=0; l<lists.size(); l+=1) { ListNode* node = lists[l]; while(node) { all[node->val] += 1; node = (*node).next; } } ListNode* tmp = nullptr; for (auto const& [key, val] : all) { int c = val; if (tmp == nullptr) { tmp = new ListNode(key); result = tmp; c -= 1; } for (int i=0; i<c; i+=1) { (*tmp).next = new ListNode(key); tmp = (*tmp).next; } } return result; } }; 

### Solution 3:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* result = nullptr; for (int l=0; l<lists.size(); l+=1) { if (lists[l] == nullptr) continue; if (result == nullptr) { result = lists[l]; continue; } ListNode *rNode = result; ListNode *lNode = lists[l]; while(lNode && rNode && lNode->val < rNode->val) { ListNode *tmp = rNode; result = lNode; lNode = lNode->next; result->next = tmp; rNode=result; } ListNode *g = result; while (lNode != nullptr){ while (rNode != nullptr && (*rNode).next) { if (rNode->next->val < lNode->val) rNode = (*rNode).next; else break; } ListNode *tmp = (*rNode).next; rNode->next = lNode; lNode = lNode->next; rNode = rNode->next; rNode->next = tmp; } } return result; } };