Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路:要快速找到k个元素中的最小值,使用堆这种数据结构。找到最小值后,还需要知道该最小值出自哪个链表,因此,堆中还需记录每个节点来自哪个链表。调整堆的时间复杂度为O(logk),所以总体时间复杂度为O(nlogk)。代码如下:
struct ListNode { int val; struct ListNode *next; }; typedef struct { int val; int index; }HeapNode; void swap(HeapNode *a, HeapNode *b) { HeapNode temp; temp = *b; *b = *a; *a = temp; } void minheapify(HeapNode *heap, int heapsize, int index) { int left, right; int key; int smallest; while(index < heapsize) { left = 2*index+1; right = 2*index+2; smallest = index; if(left < heapsize && heap[index].val > heap[left].val) { smallest = left; } if(right < heapsize && heap[smallest].val > heap[right].val) { smallest = right; } if(smallest == index) return; swap(heap+smallest, heap+index); index = smallest; } } void buildminheap(HeapNode *heap, int heapsize) { int start = (heapsize-2)/2; while(start >= 0) { minheapify(heap, heapsize, start); start--; } } struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) { int i ,j; int heapsize = listsSize; int minindex = -1; struct ListNode *head = NULL; struct ListNode *node = NULL; if(listsSize == 0) return head; HeapNode *heap = calloc(heapsize, sizeof(HeapNode)); for(i = 0, j = 0; i < heapsize; i++) { if(lists[i] == NULL) { continue; } heap[j].val = lists[i]->val; heap[j].index = i; j++; } heapsize = j; if(heapsize == 0) return head; buildminheap(heap, heapsize); minindex = heap[0].index; head = lists[minindex]; node = head; lists[minindex] = lists[minindex]->next; while(1) { if(lists[minindex] == NULL) { heapsize -= 1; if(heapsize == 0) return head; swap(heap, heap+heapsize); minheapify(heap, heapsize, 0); } else { heap[0].val = lists[minindex]->val; minheapify(heap, heapsize, 0); } minindex = heap[0].index; node->next = lists[minindex]; node = node->next; lists[minindex] = lists[minindex]->next; } }