online advertising

## Wednesday, April 1, 2015

### LeetCode OJ - Merge k Sorted Lists

Problem:

Please find the problem here.

Solution:

Conceptually, we wanted to maintain a pointer on each list, and merge them just like merge sort normally do, but we maintain k pointers together.

1  3 5 8 10
^
2  3 4 7
^
-4 -3
^

Obviously, we should pick the minimal, and advance the corresponding pointer, like this:

1  3 5 8 10
^
2  3 4 7
^
-4 -3
^

Doing this again, we exhausted the list, and we will stop on that list, but continue the algorithm

1  3 5 8 10
^
2  3 4 7
^

This requires us to be able to find out the minimum value out of the k elements. This can be done efficiently with a priority queue. So instead of having just a pointer, we have a priority of k elements.

We just do this:

Build a priority queue with all list heads.
Repeat while the priority queue still have element
Delete min and insert that to the result
If the min have a next element - insert that into the heap

Code:

#include "stdafx.h"

// https://leetcode.com/problems/merge-k-sorted-lists/

#include "LEET_MERGE_K_SORTED_LISTS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_MERGE_K_SORTED_LISTS
{
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode *mergeKLists(vector<ListNode *> &lists)
{
ListNode* head = NULL;
ListNode* tail = NULL;
ListNode** heap = new ListNode*[lists.size()];
int size = 0;

// Step 1: Initialize the heap
for (unsigned int i = 0; i < lists.size(); i++)
{
ListNode* to_insert = lists[i];
if (to_insert != NULL)
{
heap[size] = to_insert;
int current = size;
while (true)
{
if (current == 0)
{
break;
}
int parent = (current + 1) / 2 - 1;
if (heap[parent]->val > heap[current]->val)
{
swap(heap[parent], heap[current]);
current = parent;
}
else
{
break;
}
}
size++;
}
}

// Step 2: Build the result
while (size > 0)
{
// Step 2.1: Get the min
ListNode* min = heap[0];
ListNode* to_return = new ListNode(min->val);
if (head == NULL)
{
head = tail = to_return;
}
else
{
tail->next = to_return;
tail = to_return;
}

// Step 2.2: Delete min
heap[0] = heap[--size];
int current = 0;
while (true)
{
int left_child = (current + 1) * 2 - 1;
int right_child = (current + 1) * 2;
if (right_child < size)
{
if (heap[left_child]->val < heap[right_child]->val)
{
if (heap[current]->val > heap[left_child]->val)
{
swap(heap[left_child], heap[current]);
current = left_child;
}
else
{
break;
}
}
else
{
if (heap[current]->val > heap[right_child]->val)
{
swap(heap[right_child], heap[current]);
current = right_child;
}
else
{
break;
}
}
}
else if (left_child < size)
{
if (heap[left_child]->val < heap[current]->val)
{
swap(heap[left_child], heap[current]);
current = left_child;
}
else
{
break;
}
}
else
{
break;
}
}

// Step 2.3: Add the next element into the heap
if (min->next != NULL)
{
heap[size] = min->next;
current = size;
while (true)
{
if (current == 0)
{
break;
}
int parent = (current + 1) / 2 - 1;
if (heap[parent]->val > heap[current]->val)
{
swap(heap[parent], heap[current]);
current = parent;
}
else
{
break;
}
}
size++;
}
}

delete[] heap;
return head;
}
};
};

using namespace _LEET_MERGE_K_SORTED_LISTS;

int LEET_MERGE_K_SORTED_LISTS()
{
/*
[{-8,-7,-7,-5,1,1,3,4},{-2},{-10,-10,-7,0,1,3},{2}]
*/

ListNode a1(-8);
ListNode a2(-7);
ListNode a3(-7);
ListNode a4(-5);
ListNode a5(1);
ListNode a6(1);
ListNode a7(3);
ListNode a8(4);

ListNode b1(-2);

ListNode c1(-10);
ListNode c2(-10);
ListNode c3(-7);
ListNode c4(0);
ListNode c5(1);
ListNode c6(3);

ListNode d1(2);

a1.next = &a2;
a2.next = &a3;
a3.next = &a4;
a4.next = &a5;
a5.next = &a6;
a6.next = &a7;
a7.next = &a8;
a8.next = NULL;

c1.next = &c2;
c2.next = &c3;
c3.next = &c4;
c4.next = &c5;
c5.next = &c6;
c6.next = NULL;

vector<ListNode*> lists;
lists.push_back(&a1);
lists.push_back(&b1);
lists.push_back(&c1);
lists.push_back(&d1);
Solution solution;
ListNode* sorted = solution.mergeKLists(lists);
while (sorted != NULL)
{
cout << sorted->val << " ";
sorted = sorted->next;
}
cout << endl;

return 0;
}