Leetcode notes No.21

21. Merge two ordered lists

Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .

Example ：
Input ：1->2->4, 1->3->4
Output ：1->1->2->3->4->4

The data type is defined in the title ：

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

analysis

My idea is ：
Create a head node as a new starting point , from l1 and l2 The heads of the two ordered linked lists begin to compare , Because the requirements are in ascending order , So the smaller one is assigned to the head node first next, Then the pointer moves back

Answer key

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    
    struct ListNode* o = (struct ListNode*)malloc(sizeof(struct ListNode));
    o->next = NULL;
    struct ListNode* temp = o;
    while(l1 != NULL && l2 != NULL) {
    
        
        if (l1->val < l2->val) {
    
            o->next = l1;
            o = o->next;
            l1 = l1->next;
        }
        else {
    
            o->next = l2;
            o = o->next;
            l2 = l2->next;
        }
    }
    if (l1 != NULL && l2 == NULL) {
    
        o->next = l1;
    }
    else if (l1 == NULL && l2 != NULL) {
    
        o->next = l2;
    }

    o = temp->next;
    free(temp);
    return o;
}

Be careful

 o->next = NULL;

I didn't write this code at first ( Not fully considered ). stay l1 and l2 When both linked lists are empty , Neither the cycle nor the following judgment will go to , Not writing this code means o->next It's a random address ( because malloc It will not automatically help us initialize the requested memory space ), This address is not governed by this program , So it belongs to illegal access . We return this random address , If it's just reading, it won't cause any serious problems , If you write values inside , Then the consequences deserve attention .
summary
Remember to initialize the address before using ！！！
Remember to initialize the address before using ！！！
Remember to initialize the address before using ！！！