Simple linear C solution


  • 0
    D

    We create a head node, then we move on searching through list l1 and l2 to see whoever's next node has a smaller value, we attach that node to head->next. In this method, we don't create any extra spaces for storing lists. Instead, pointers to lists' nodes are manipulated.

    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        struct ListNode *head, *tail, *temp;
        
        if( l1 == NULL || l2 == NULL ) /* if one of them is NULL, return the other */
            return ( l1 == NULL ? l2 : l1 );
        
        /* head points to the list that has a smaller head */
        if( l1->val < l2->val ) {
            head = l1;
            l1 = l1->next;
        }
        else {
            head = l2;
            l2 = l2->next;
        }
        
        tail = head;
        while( l1 != NULL && l2 != NULL ) {
            if( l1->val < l2->val ) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = ( l1 == NULL ? l2 : l1 );
        return head;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.