[LeetCode 23] Merge k Sorted Lists [C, Java] [Runtime : 9 MS]

1. Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

2. Example

3. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

void swap(struct ListNode ** node1, struct ListNode ** node2)
{
	struct ListNode * tmp = *node1; *node1 = *node2; *node2 = tmp;
}

struct ListNode * adjustHeap(struct ListNode ** nums, int numsSize, int i)
{
	while(i < numsSize >> 1)
	{
		int child = (i << 1) + 2 < numsSize ? nums[(i << 1) + 1]->val > nums[(i << 1) + 2]->val ? (i << 1) + 2 : (i << 1) + 1 : (i << 1) + 1;

		if(nums[i] -> val <= nums[child]->val)
		{
			return nums[0];
		}
		swap(&nums[i], &nums[child]); i = child;
	}
	return nums[0];
}

void createHeap(struct ListNode ** nums, int numsSize)
{
	for(int i = (numsSize >> 1) -1; i >= 0; i--)
	{
		adjustHeap(nums, numsSize, i);
	}
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {

	struct ListNode ** heap = malloc(listsSize * sizeof(struct ListNode));

	int count = 0;

	for(int i = 0; i< listsSize; i++)
	{
		if(lists[i] != NULL)
		{
			heap[count++] = lists[i];
		}
	}

	if (count == 0)
	{
		return NULL;
	}

	createHeap(heap, count);

	struct ListNode * result = heap[0];
	struct ListNode * current = result;

	while(current != NULL)
	{
		if(current -> next != NULL || count == 1)
		{
			heap[0] = current->next;
		}else if(count > 1)
		{
			heap[0] = heap[--count];
		}

		adjustHeap(heap, count, 0);
		current->next = heap[0];
		current = current->next;
	}

	return result;
}

[/restab]
[restab title="Java"]

public ListNode mergeKLists(ListNode[] lists) {
	
	if(lists == null || lists.length == 0){
		return null;
	}
	
	Comparator compare = new Comparator(){
		@Override
		public int compare(ListNode c1, ListNode c2) {
			return c1.val - c2.val;
		}
	};
	 
	PriorityQueue queue = new PriorityQueue(lists.length, compare);
	
	ListNode head = new ListNode(0);
	ListNode tail = head;
	
	for(ListNode listNode: lists){
		if(listNode != null){
			queue.add(listNode);
		}
	}
	
	while(!queue.isEmpty()){
		tail.next = queue.poll();
		tail = tail.next;
		
		if(tail.next != null){
			queue.add(tail.next);
		}
	}
	return head.next;
}

[/restab]
[/restabs]

4.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 

struct ListNode
{
	int val;
	struct ListNode * next;
};

void swap(struct ListNode ** node1, struct ListNode ** node2)
{
	struct ListNode * tmp = *node1; *node1 = *node2; *node2 = tmp;
}

struct ListNode * adjustHeap(struct ListNode ** nums, int numsSize, int i)
{
	while(i < numsSize >> 1)
	{
		int child = (i << 1) + 2 < numsSize ? nums[(i << 1) + 1]->val > nums[(i << 1) + 2]->val ? (i << 1) + 2 : (i << 1) + 1 : (i << 1) + 1;

		if(nums[i] -> val <= nums[child]->val)
		{
			return nums[0];
		}
		swap(&nums[i], &nums[child]); i = child;
	}
	return nums[0];
}

void createHeap(struct ListNode ** nums, int numsSize)
{
	for(int i = (numsSize >> 1) -1; i >= 0; i--)
	{
		adjustHeap(nums, numsSize, i);
	}
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {

	struct ListNode ** heap = malloc(listsSize * sizeof(struct ListNode));

	int count = 0;

	for(int i = 0; i< listsSize; i++)
	{
		if(lists[i] != NULL)
		{
			heap[count++] = lists[i];
		}
	}

	if (count == 0)
	{
		return NULL;
	}

	createHeap(heap, count);

	struct ListNode * result = heap[0];
	struct ListNode * current = result;

	while(current != NULL)
	{
		if(current -> next != NULL || count == 1)
		{
			heap[0] = current->next;
		}else if(count > 1)
		{
			heap[0] = heap[--count];
		}

		adjustHeap(heap, count, 0);
		current->next = heap[0];
		current = current->next;
	}

	return result;
}

int main()
{
	struct ListNode * ln11 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln11->val = 1;
	struct ListNode * ln12 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln12->val = 2;
	struct ListNode * ln13 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln13->val = 2;
	ln11->next = ln12;
	ln12->next = ln13;
	ln13->next = NULL;

	struct ListNode * ln21 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln21->val = 1;
	struct ListNode * ln22 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln22->val = 1;
	struct ListNode * ln23 = (struct ListNode *)malloc(sizeof(struct ListNode));
	ln23->val = 2;
	ln21->next = ln22;
	ln22->next = ln23;
	ln23->next = NULL;

	struct ListNode * lists[] = { ln11,ln21 };

	struct ListNode * result = mergeKLists(lists, 2);

	while(result != NULL)
	{
		printf("%d", result->val);
		result = result -> next;
	}
	printf("\n");
	system("pause");
	return 0;
}

[/restab]
[restab title="java"]

import java.util.Comparator;
import java.util.PriorityQueue;

import org.junit.Test;

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
}

public class LeetCode0023 {
	public ListNode mergeKLists(ListNode[] lists) {
		
		if(lists == null || lists.length == 0){
			return null;
		}
		
		Comparator compare = new Comparator(){
			@Override
			public int compare(ListNode c1, ListNode c2) {
				return c1.val - c2.val;
			}
		};
		 
		PriorityQueue queue = new PriorityQueue(lists.length, compare);
		
		ListNode head = new ListNode(0);
		ListNode tail = head;
		
		for(ListNode listNode: lists){
			if(listNode != null){
				queue.add(listNode);
			}
		}
		
		while(!queue.isEmpty()){
			tail.next = queue.poll();
			tail = tail.next;
			
			if(tail.next != null){
				queue.add(tail.next);
			}
		}
		return head.next;
    }
	
	@Test
	public void test(){
		ListNode ln11 = new ListNode(1);
		ListNode ln12 = new ListNode(2);
		ListNode ln13 = new ListNode(2);
		ln11.next = ln12;
		ln12.next = ln13;
		ln13.next = null;
		
		ListNode ln21 = new ListNode(1);
		ListNode ln22 = new ListNode(1);
		ListNode ln23 = new ListNode(2);
		ln21.next = ln22;
		ln22.next = ln23;
		ln23.next = null;
		
		ListNode[] listNode = {ln11, ln21};
		
		ListNode result = mergeKLists(listNode);
		
		while(result != null){
			System.out.print(result.val);
			result = result.next;
		}
	}
}

[/restab]
[/restabs]