从c中的一个链表数组中返回一个已排序的列表

Question

最后我要完成的是对一个包含多个链表的结构数组进行排序，并返回1个合并列表并进行排序。

示例

Input: [1->4->5, 1->3->4, 2->6] 
Output: 1->1->2->3->4->4->5->6 

输入是数组，如示例中所示，该数组中有3个不同的列表排序错误。

输出是最终排序的列表。

我试图做的是像访问普通结构数组一样访问数组，然后一次将其排序为2。

我的代码

#include <stddef.h>

#ifndef STRUCT_LISTNODE
#define STRUCT_LISTNODE
typedef struct s_listnode
{
int val;
struct s_listnode* next;
} listnode;
#endif
#ifndef STRUCT_LISTNODE_ARRAY
#define STRUCT_LISTNODE_ARRAY
typedef struct s_listnode_array
{
int size;
listnode **array;
} listnode_array;
#endif

listnode* sort(listnode* first, listnode* second){
listnode* newNode;
if(first == NULL && second == NULL)
return NULL;
if (first == NULL)
return second;
if (second == NULL)
return first;
// checking if the value on the first list bigger than the second or equal
if (first->val >= second->val) {
// if yes that means that the second should be first.
newNode = second;
newNode->next = sort(first, second->next);
} else {
newNode = first;
newNode->next = sort(first->next, second);
}
return newNode;
}
listnode* merge_k_sorted_lists(listnode_array* head)
{
listnode *newNode;
for(int i = 0 ; i < head->size; i++){
newNode = sort(head->array[0], head->array[i]);
}
return newNode;
}

当我尝试运行我的代码时，我根本没有得到任何返回值。

Answer 1

我做了一些更改，现在它似乎工作得更好，但存在问题。

如果输入是一个有[[]，[1]]的数组，并且预期输出应该是[1]，那么我不会得到返回，而是得到SIGSEGV(信号11(

#include <stddef.h>

#ifndef STRUCT_LISTNODE
#define STRUCT_LISTNODE
typedef struct s_listnode
{
int val;
struct s_listnode* next;
} listnode;
#endif
#ifndef STRUCT_LISTNODE_ARRAY
#define STRUCT_LISTNODE_ARRAY
typedef struct s_listnode_array
{
int size;
listnode **array;
} listnode_array;
#endif

listnode* sort(listnode* first, listnode* second){

if(first == NULL && second == NULL)
return NULL;
if (first == NULL){
return second;
}
if (second == NULL)
return first;

listnode* newNode;

if (first->val > second->val) {
newNode = second;
newNode->next = sort(first, second->next);
} else {
newNode = first;
newNode->next = sort(first->next, second);
}
return newNode;
}

listnode* merge_k_sorted_lists(listnode_array* nodeArr)
{
listnode *newNode;

if(nodeArr->array[0]->next == NULL) 
return nodeArr->array[0];
if(nodeArr->size < 2)
return nodeArr->array[0];
for(int i = 1 ; i < nodeArr->size; i++)
newNode = sort(nodeArr->array[0], nodeArr->array[i]);
return newNode;
}

Answer 2

修复并简化了merge_k_sorted_lists((。从sort((中删除了一个不需要的if语句。这与链表自下而上合并排序中的第二个循环基本相同。递归排序((实际上是一个合并，它将导致大型列表的堆栈溢出。

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

#include <stdio.h>
#ifndef STRUCT_LISTNODE
#define STRUCT_LISTNODE
typedef struct s_listnode
{
int val;
struct s_listnode* next;
} listnode;
#endif
#ifndef STRUCT_LISTNODE_ARRAY
#define STRUCT_LISTNODE_ARRAY
typedef struct s_listnode_array
{
int size;
listnode **array;
} listnode_array;
#endif
listnode* sort(listnode* first, listnode* second){
listnode* newNode;
if (first == NULL)
return second;
if (second == NULL)
return first;
if (first->val > second->val) {
newNode = second;
newNode->next = sort(first, second->next);
} else {
newNode = first;
newNode->next = sort(first->next, second);
}
return newNode;
}
listnode* merge_k_sorted_lists(listnode_array* nodeArr)
{
listnode *newNode = NULL;
for(int i = 0 ; i < nodeArr->size; i++)
newNode = sort(newNode, nodeArr->array[i]);
return newNode;
}
int main()
{
listnode list0[3] = {{1, list0+1}, {4,list0+2}, {5,NULL}};
listnode list1[3] = {{1, list1+1}, {3,list1+2}, {4,NULL}};
listnode list2[2] = {{2, list2+1}, {6,NULL}};
listnode *lists[3] = {list0, list1, list2};
listnode_array array[3] = {3, lists};
listnode *result, *tmp;
result = merge_k_sorted_lists(array);
for(tmp = result; tmp; tmp = tmp->next)
printf("%1d ", tmp->val);
printf("n");
return 0;
}

---

使用伪节点的非递归合并

listnode* sort(listnode* first, listnode* second){
listnode dMrg = {0, NULL};              /* dummy node */
listnode *pMrg = &dMrg;                 /* ptr to node in merged list */
if (first == NULL)                  /* check for empty lists */
return second;
if (second == NULL)
return first;
while(1){                           /* merge the lists */
if(first->val > second->val){
pMrg = pMrg->next = second;
second = second->next;
if(second == NULL){
pMrg->next = first;
break;
}
}else{
pMrg = pMrg->next = first;
first = first->next;
if(first == NULL){
pMrg->next = second;
break;
}
}
}
return dMrg.next;                   /* return merged list */
}

---

使用指针到指针的非递归合并

listnode* sort(listnode* first, listnode* second){
listnode *pMrg;                         /* merged list */
listnode **ppMrg = &pMrg;               /* ptr to ptr to node in merged list */
if (first == NULL)                  /* check for empty lists */
return second;
if (second == NULL)
return first;
while(1){                           /* merge the lists */
if(first->val > second->val){
*ppMrg = second;
ppMrg = &(second->next);
second = *ppMrg;
if(second == NULL){
*ppMrg = first;
break;
}
}else{
*ppMrg = first;
ppMrg = &(first->next);
first = *ppMrg;
if(first == NULL){
*ppMrg = second;
break;
}
}
}
return pMrg;
}