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

Question

I would like to ask why this link list will not run the result. After running, it is TLE. I want the head to be an indicator, and the head list can be returned without modifying the 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

The function has undefined behavior because the pointer head and correspondingly the pointer node are not initialized

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

To make this assignment correct

node->next = list1;

you need initially to define a dummy node and set the pointer node to the address of the node.

The while loops like this

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

in fact are redundant. In fact it is enough to write

node->next = list1;

or

node->next = list2; 

Also the function does not change the original pointers of the two lists passed to the function as arguments.

The function should be declared and defined the following way as shown in the demonstration program below.

#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 );
}

The program output is

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