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

CodePudding user response：

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

CodePudding user response：

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

Output:

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