I have the following code to merge two sorted linked lists:

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    ListNode    *out = NULL;

    while (list1 != NULL || list2 != NULL){
        if (list1->val <= list2->val){
            if (out != NULL){
                out->next = list1;
                out = out->next;
            }
            else {
                out = list1;
            }
            list1 = list1->next;
        }
        else {
            if (out != NULL){
                out->next = list2;
                out = out->next;
            }
            else {
                out = list2;
            }
            list2 = list2->next;
        }
    }
    return (out);
}

However I will get a runtime error on the first if because I'm not checking if they are null or not.

Is there any clean way to do this?

CodePudding user response：

TomKarzes answer is the best and yields something like:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    ListNode    *head = NULL;
    ListNode    *temp = NULL;

    while (list1 != NULL || list2 != NULL){
        if (list1 && list2 && list1->val <= list2->val){
            if (head != NULL){
                temp->next = list1;
                temp = temp->next;
            }
            else {
                head = list1;
                temp = head;
            }
            list1 = list1->next;
        }
        else if (list1 && list2 && list1->val > list2->val){
            if (head != NULL){
                temp->next = list2;
                temp = temp->next;
            }
            else {
                head = list2;
                temp = head;
            }
            list2 = list2->next;
        }
        else if (!list2 && list1){
            if (head != NULL){
                temp->next = list1;
                temp = temp->next;
            }
            else {
                head = list1;
                temp = head;
            }
            list1 = list1->next;
        }
        else if (!list1 && list2){
            if (head != NULL){
                temp->next = list2;
                temp = temp->next;
            }
            else {
                head = list2;
                temp = head;
            }
            list2 = list2->next;
        }
    }
    return (head);
}

Which has a lot of repeated code hence a recursive approach might be cleaner:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        if (!list1)
            return list2;
        else if (!list2)
            return list1;
        else if (list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else if (list1->val > list2->val){
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
        return NULL;
}

CodePudding user response：

It doesn’t get any cleaner than if (node).

Since you have typedefed your struct type, you can drop the struct keyword when you use it.

Be careful with your out: presumably you want to return the head of the new list, and not the tail. You’ll have to keep track of the new head (to return to the caller) and the tail (for appending) separately. Fortunately there’s a cool trick you can use.

As Tom Karzes mentioned in his comment, the common way to perform a merge is with three loops, two of which will be used. Since we are messing with linked lists, the final two loops reduce to a simple test-and-join each:

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
  ListNode  head = { 0, NULL };  // faux head node
  ListNode* tail = &head;        // tail node for appending

  // While (list1 has elements) and (list2 has elements)..
  while (list1 && list2)
  {
    // ..extract head of list1 or list2 and append it to tail
    if (list2->val < list1->val) { tail->next = list2; list2 = list2->next; }
    else                         { tail->next = list1; list1 = list1->next; }
    tail = tail->next;  // update tail to true tail
    tail->next = NULL;  // (finish unlinking head of list1 or list2)
  }

  // If (list1 has any remaining elements)..
  if (list1)
    tail->next = list1;  // ..append it to tail

  // If (list2 has any remaining elements)..
  if (list2)
    tail->next = list2;  // ..append it to tail

  // Return the merged lists (without our faux head, of course)
  return head->next;
}

Notice how we don’t bother to try to find the tail again between the last two loops test-and-joins? This is because a maximum of only one of the conditions will be true, right?

Also, recursion is a cool trick, but in languages like C (and C ) you should generally opt away from it over large lists — especially when a simple loop will do. It is far too easy to smash the stack with code that cannot be optimized with tailcall recursion, such as MiguelP’s otherwise very cool example.