合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围:节点总数 ,每个节点的val满足
要求:时间复杂度
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类一维数组 * @param listsLen int lists数组长度 * @return ListNode类 */ int lenth(struct ListNode* p1, struct ListNode* p2){ int len = 0; while(p1 != NULL){ len++; p1 = p1->next; } while(p2 != NULL){ len++; p2 = p2->next; } return len; } void mergeSort(struct ListNode* p1, struct ListNode* p2, int len){ int* B = (int*)malloc(sizeof(int)*len), k = 0; struct ListNode* p3, *p4; p3 = p1; p4 = p2; while(p3 != NULL && p4 != NULL){ if(p3->val <= p4->val){ B[k++] = p3->val; p3 = p3->next; }else{ B[k++] = p4->val; p4 = p4->next; } } while(p3 != NULL){ B[k++] = p3->val; p3 = p3->next; } while(p4 != NULL){ B[k++] = p4->val; p4 = p4->next; } p3 = p1; while(p3->next != NULL){ p3 = p3->next; } p3->next = p2; for(p3 = p1,k =0;k < len;k++){ p3->val = B[k]; p3 = p3->next; } free(B); } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here struct ListNode* p1 = NULL, *p2 = NULL; int i = 0,j,Lenth; while(lists[i] == NULL && i < listsLen){ i++; } p1 = lists[i]; if(i != listsLen - 1){ for(j = i + 1;j < listsLen;j++){ p2 = lists[j]; Lenth = lenth(p1,p2); mergeSort(p1, p2, Lenth); } return p1; }else{ return p1; } }
void AddListNode(struct ListNode** head, int m, int val) { struct ListNode *NewNode,*p1; NewNode = (struct ListNode *)malloc(sizeof(struct ListNode)); NewNode->val = val; if(!m) { NewNode->next = *head; *head = NewNode; return; } p1 = *head; while((--m>0)&&(p1->next!=NULL)) p1 = p1->next; { struct ListNode *buffer; buffer = p1->next; p1->next = NewNode; NewNode->next = buffer; } } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { struct ListNode *res=NULL,*p1,*p2; if(!listsLen) return NULL; res = mergeKLists(lists, listsLen-1); p1 = lists[listsLen-1]; if(p1 == NULL) return res; if(res == NULL) return p1; do { int AddLoc = 0; p2 = res; do { if(p1->val <= p2->val) { AddListNode(&res, AddLoc, p1->val); break; } AddLoc++; p2 = p2->next; }while(p2 != NULL); if(p2 == NULL) AddListNode(&res, AddLoc, p1->val); p1 = p1->next; }while(p1 != NULL); return res; }这是我第一次完全自己调通的稍微复杂的递归,总结一句:特殊情况必须考虑,不然递归不通。我没有看解题思路,肯定没有官方的好,不算是最好的代码,但已经成就满满。高手解题思路才是真正的简。
#include <stdlib.h> struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here struct ListNode* head = NULL; struct ListNode* p = *lists; struct ListNode* t = (struct ListNode*)malloc(sizeof(struct ListNode)); //归并后序列 head = t; for(int i = 1; i < listsLen; i++) { struct ListNode* q = lists[i]; while (p != NULL || q != NULL) { if(p == NULL) { t->next = q; break; } if(q == NULL) { t->next = p; break; } if(p->val < q->val) { t->next = p; p = p->next; t = t->next; } else { t->next = q; q = q->next; t = t->next; } } p = head->next; t = head; } head = head->next; return head; }
#include <stdlib.h> int s[5000]; int privot(int a[], int low, int high); void quicksort(int a[], int low, int high); struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here int i = 0; int j = 0; struct ListNode *p; //将所有链表的值赋给数组s for (j = 0; j < listsLen; j++){ p = lists[j]; while(p) { s[i++] = p->val; p = p->next; } } //对数组s进行快排 quicksort(s, 0, i-1); struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode)); q->next = NULL; p = q; //将排好序的值一一赋给新的链表 for (j = 0; j < i; j++){ struct ListNode *r = (struct ListNode *)malloc(sizeof(struct ListNode)); r->val = s[j]; r->next = NULL; p->next = r; p = p->next; } return q->next; } //划分 int privot(int a[], int low, int high) { int temp = a[low]; while (low < high){ while (low < high && a[high] >= temp) high--; a[low] = a[high]; while (low < high && a[low] <= temp) low++; a[high] = a[low]; } a[low] = temp; return low; } //快排 void quicksort(int a[], int low, int high){ if (low < high) { int pri = privot(a, low, high); quicksort(a, low, pri-1); quicksort(a, pri+1, high); } }
/** * 合并两个链表 */ struct ListNode *mergeList(struct ListNode *left, struct ListNode *right) { struct ListNode *head = malloc(sizeof(struct ListNode)); struct ListNode *node = head; while (left && right) { if (left->val < right->val) { node->next = left; left = left->next; } else { node->next = right; right = right->next; } node = node->next; } node->next = left ? left : right; node = head->next; free(head); return node; } /** * @description 头尾链表合并到一起,更新头链表,直到只剩下一个链表 * @param lists ListNode类一维数组 * @param listsLen int lists数组长度 * @return ListNode类 */ struct ListNode *mergeKLists(struct ListNode **lists, int listsLen) { // write code here if (listsLen <= 0) { return NULL; } int st = 0, ed = listsLen - 1; while (ed > 0) { st = 0; while (st < ed && ed) { lists[st] = mergeList(lists[st], lists[ed]); st++; ed--; } } return lists[0]; }
/** * * @param lists ListNode类一维数组 * @param listsLen int lists数组长度 * @return ListNode类 */ struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here struct ListNode* head = NULL; int i = 0; for(i = 0; i < listsLen; i++) { struct ListNode* ptr1 = lists[i]; if(ptr1 == NULL) continue; if(head == NULL) { head = ptr1; continue; } struct ListNode* ptr2 = head, *ptr3 = NULL; while(ptr1 != NULL && ptr2 != NULL) { if(ptr1->val >= ptr2->val && ptr2->next != NULL && ptr1->val <= ptr2->next->val){ ptr3 = ptr1->next; ptr1->next = ptr2->next; ptr2->next = ptr1; ptr1 = ptr3; ptr2 = ptr2->next; }else if(ptr1->val < ptr2->val){ head = ptr1; ptr3 = ptr1->next; ptr1->next = ptr2; ptr2 = ptr1; ptr1 = ptr3; }else if(ptr2->next == NULL){ ptr2->next = ptr1; break; }else{ ptr2 = ptr2->next; } } if(ptr1 != NULL && ptr2 == NULL) { ptr2->next = ptr1; } } return head; }
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen) { // write code here if (listsLen == 1) return lists[0]; struct ListNode* newNodeBegin[2002]; struct ListNode* newNodeEnd[2002]; struct ListNode* node; struct ListNode* nodeNext; for (int i = 0; i < listsLen; ++i) { node = lists[i]; while (node != NULL) { nodeNext = node->next; node->next = NULL; if (newNodeBegin[node->val + 1000] == NULL) { newNodeBegin[node->val + 1000] = node; newNodeEnd[node->val + 1000] = node; } else { node->next = newNodeBegin[node->val + 1000]; newNodeBegin[node->val + 1000] = node; } node = nodeNext; } } node = NULL; nodeNext = NULL; for (int i = 0; i <= 2000; ++i) { if (newNodeBegin[i] != NULL) { if (node == NULL) { node = newNodeBegin[i]; nodeNext = newNodeEnd[i]; } else { nodeNext->next = newNodeBegin[i]; nodeNext = newNodeEnd[i]; } } } return node; } //简单粗暴,题目给定了val的取值范围,直接弄一个2000的数组。先把每个val值相同节点的串起来。然后重小到大循环再链接一次 //这样 你甚至可以传入不是排好序的链表
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { int i = 0; struct ListNode *newhead = lists[0]; int flag = 1; if(!listsLen) { return lists[0]; } while(i != listsLen) { struct ListNode *p; if(lists[i]) { if(flag) { newhead = lists[i]; flag = 0; } if(i == listsLen-1) break; p = lists[i]; while(p->next) { p = p->next; } while(!lists[++i]) { if(i == listsLen-1) { break; } } p->next = lists[i]; } else { i++; } } struct ListNode *q = NULL; struct ListNode *temp; int val; struct ListNode *p = newhead; while(p) { temp = p; q = p; while(q) { if(temp->val > q->val) { temp = q; } q = q->next; } val = p->val; p->val = temp->val; temp->val = val; p = p->next; } return newhead; // write code here }
int CheckPHead(struct ListNode** lists,int listsLen);//检查是否只有一个头节点不为0 struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here struct ListNode* nh=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* sh=nh; struct ListNode* lmin=0; while(CheckPHead(lists,listsLen)){ int min=1001;//j最小值的索引 for(int i=0;i<listsLen;i++){ //找出最小值 if(lists[i]!=0){ if(min>lists[i]->val){ min=lists[i]->val; } } } for(int i=0;i<listsLen;i++){ //链接 if(lists[i]!=0){ if(lists[i]->val==min){ nh->next=lists[i];nh=lists[i]; lists[i]=lists[i]->next; } } } } for(int i=0;i<listsLen;i++){ //链接最长的结点 if(lists[i]!=0){ nh->next=lists[i]; } } return sh->next; } int CheckPHead(struct ListNode** lists,int listsLen){ int count=0; for(int i=0;i<listsLen;i++){ if(lists[i]!=0){ count++; } } if(count<=1){ return 0; }else{ return 1; } }
C语言实现方法: 基本思路:归并排序法,递归排序 struct ListNode* sort(struct ListNode* l, struct ListNode* r) { struct ListNode head = {0}; struct ListNode* cur = &head; while (l != NULL && r != NULL) { if (l->val <= r->val) { cur->next = l; cur = cur->next; l = l->next; } else { cur->next = r; cur = cur->next; r = r->next; } } if (l != NULL) { cur->next = l; } if (r != NULL) { cur->next = r; } return head.next; } struct ListNode* mergesort(struct ListNode** lists, int left, int right) { int mid = 0; struct ListNode *l = NULL, *r = NULL; if (left < right) { mid = (left + right) / 2; l = mergesort(lists, left, mid); r = mergesort(lists, mid + 1, right); return sort(l, r); } else { return lists[left]; } } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { return mergesort(lists, 0, listsLen - 1); }