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; } Comparatorcompare = 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; } Comparatorcompare = 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]
Comments | NOTHING