Leetcode:Merge 两个排序列表。我不知道link哪里错了

Question

请问为什么这个link列表不会运行结果。运行ning之后就是TLE了。我想让head做一个指标，不用修改head就可以返回head列表

/**
 * 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

Leetcode:Merge 两个排序列表。我不知道link哪里错了

Leetcode:Merge Two Sorted Lists. I don't know where the link is wrong

c

struct

merge

singly-linked-list

function-definition