c语言 - Leetcode：合并两个排序列表。我不知道链接哪里错了

Question

我想问一下为什么这个链接列表不会运行结果。跑完之后，就是TLE。我希望头部是一个指示器，并且可以在不修改头部的情况下返回头部列表。

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(!list1 && !list2) return NULL;

struct ListNode *head;
struct ListNode *node = head;
while(list1 && list2){
if(list1->val < list2->val){
node->next = list1;
list1 = list1->next;
node = node->next;
}
else{
node->next = list2;
list2 = list2->next;
node = node->next;
}
}
if(list1){
while(list1){
node->next = list1;
list1 = list1->next;
node = node->next;
}
}
if(list2){
while(list2){
node->next = list2;
list2 = list2->next;
node = node->next;
}  
}
return head->next;
}

Answer 1

函数有未定义的行为，因为指针头和相应的指针节点没有初始化

struct ListNode *head;
struct ListNode *node = head;
while(list1 && list2){
if(list1->val < list2->val){
node->next = list1;
//... 

为了使此分配正确

node->next = list1;

最初需要定义一个伪节点，并将指针node设置为该节点的地址。

while像这个一样循环

while(list1){
node->next = list1;
list1 = list1->next;
node = node->next;
}

事实上是多余的。事实上，写就足够了

node->next = list1;

或

node->next = list2; 

此外，函数不会更改作为参数传递给函数的两个列表的原始指针。

应按照以下演示程序所示的方式声明和定义函数。

#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode
{
int val;
struct ListNode *next;
} ListNode;
void clear( ListNode **head )
{
while (*head)
{
ListNode *current = *head;
*head = ( *head )->next;
free( current );
}
}
size_t assign( ListNode **head, const int a[], size_t n )
{
clear( head );
size_t i = 0;
for (; i != n && ( *head = malloc( sizeof( ListNode ) ) ) != NULL; i++)
{
( *head )->val = a[i];
( *head )->next = NULL;
head = &( *head )->next;
}
return i;
}
FILE *display( const ListNode *const head, FILE *fp )
{
for (const ListNode *current = head; current != NULL; current = current->next)
{
fprintf( fp, "%d -> ", current->val );
}
fputs( "null", fp );
return fp;
}
struct ListNode *mergeTwoLists( struct ListNode **list1, struct ListNode **list2 )
{
struct ListNode *head = NULL;
struct ListNode **current = &head;
struct ListNode *head1 = *list1;
struct ListNode *head2 = *list2;
while ( head1 && head2 )
{
if ( head2->val < head1->val )
{
*current = head2;
head2 = head2->next;
}
else
{
*current = head1;
head1 = head1->next;
}
current = &( *current )->next;
}
if ( head1 )
{
*current = head1;
}
else if ( head2 )
{
*current = head2;
}
*list1 = NULL;
*list2 = NULL;
return head;
}
int main( void )
{
struct ListNode *head1 = NULL;
struct ListNode *head2 = NULL;
int a[] = { 0, 2, 4, 6, 8 };
assign( &head1, a, sizeof( a ) / sizeof( *a ) );
int b[] = { 1, 3, 5, 7, 9 };
assign( &head2, b, sizeof( b ) / sizeof( *b ) );
fputc( 'n', display( head1, stdout ) );
fputc( 'n', display( head2, stdout ) );
struct ListNode *head3 = mergeTwoLists( &head1, &head2 );
fputc( 'n', display( head3, stdout ) );
clear( &head3 );
}

程序输出为

0 -> 2 -> 4 -> 6 -> 8 -> null
1 -> 3 -> 5 -> 7 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Answer 2

#include <stdio.h>
#include <stdlib.h>

// A nested list node
struct ListNode
{
int val;
struct ListNode *next;
};

// Add a node
void add(struct ListNode ** head_ref, int new_val)
{
struct ListNode* new_node =  (struct ListNode*) malloc(sizeof(struct ListNode));
new_node->val  = new_val;
new_node->next = (*head_ref);
(*head_ref)  = new_node;
}

// Merge nodes of linked list src into dest
void merge(struct ListNode *dest, struct ListNode **src)
{
struct ListNode *dest_curr = dest, *src_curr = *src;
struct ListNode *dest_next, *src_next;

// While there are available positions in dest
while (dest_curr != NULL && src_curr != NULL)
{
// Save next pointers
dest_next = dest_curr->next;
src_next = src_curr->next;

// Make src_curr as next of dest_curr  
// Change next pointer of src_curr
src_curr->next = dest_next;  

// Change next pointer of dest_curr
dest_curr->next = src_curr;  

// Update current pointers for next iteration
dest_curr = dest_next;
src_curr = src_next;
}

// Update head pointer of second list
*src = src_curr; 
}

// Print linked list
void print(struct ListNode *head)
{
struct ListNode *temp = head;
while (temp != NULL)
{
printf("%d ", temp->val);
temp = temp->next;
}
printf("n");
}
int main()
{
struct ListNode *dest = NULL, *src = NULL;
add(&dest, 2);
add(&dest, 1);
printf("First List: ");
print(dest);

add(&src, 4);
add(&src, 3);
printf("Second List: ");
print(src);

merge(dest, &src);

printf("Merger Lists: ");
print(dest);

getchar();
return 0;
}

输出：

First List: 1 2 
Second List: 3 4 
Merger Lists: 1 3 2 4