Thread: How can I optimize this function that merges two ordered linked lists?

  1. #1
    Registered User
    Join Date
    Mar 2020
    Posts
    10

    How can I optimize this function that merges two ordered linked lists?

    I am learning data structures in C and, in one exercise, I was asked to create a function that merges two ordered linked lists into a single ordered linked list. Here it is:


    Code:
    static struct listnode *
    merge(struct listnode *a, struct listnode *b)
    {
        struct listnode *head, *p;
    
        if (a == NULL)
            return b;
        if (b == NULL)
            return a;
    
        if (a->data <= b->data) {
            p = head = a;
            a = a->next;
        }
        else {
            p = head = b;
            b = b->next;
        }
    
        while (a != NULL && b != NULL) {
            if (a->data <= b->data) {
                p->next = a;
                a = a->next;
            } else {
                p->next = b;
                b = b->next;
            }
            p = p->next;
        }
    
        if (a != NULL)
            p->next = a;
        if (b != NULL)
            p->next = b;
    
        return head;
    }
    But it is full of ifs and repeated conditions, and I think my function is unnecessarily verbose. How can I optimize this function to something more short and elegant?


    Here's the struct:

    Code:
    struct listnode {
        char data;
        struct listnode *next;
    };
    Last edited by felixthunder; 03-20-2020 at 07:35 PM.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    928
    Code:
    typedef struct listnode {
        char data;
        struct listnode *next;
    } ListNode;
    Code:
    ListNode *merge(ListNode *a, ListNode *b)
    { 
        ListNode *head = NULL, **curr = &head;
     
        while (a && b) {
            if (a->data <= b->data) {
                *curr = a;
                a = a->next;
            } else {
                *curr = b;
                b = b->next;
            }
            curr = &(*curr)->next;
        }
     
        if (a) *curr = a;
        if (b) *curr = b;
     
        return head;
    }
    Or recursively (but "inefficient" since it's not tail recursion) :
    Code:
    ListNode *merge2(ListNode *a, ListNode *b )
    {
        if (a && (!b || a->data <= b->data))
        {
            a->next = merge2(a->next, b);
            return a;
        }
        else if (b)
        {
            b->next = merge2(a, b->next);
            return b;
        }
        return NULL;
    }
    Last edited by john.c; 03-20-2020 at 09:36 PM.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    928
    The recursive version is better written like this:
    Code:
    ListNode *merge2(ListNode *a, ListNode *b )
    {
        if (!a) return b;
        if (!b) return a;
     
        if (a->data <= b->data)
        {
            a->next = merge2(a->next, b);
            return a;
        }
     
        b->next = merge2(a, b->next);
        return b;
    }
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  4. #4
    Registered User
    Join Date
    Mar 2020
    Posts
    10
    Quote Originally Posted by john.c View Post
    Code:
         ListNode *head = NULL, **curr = &head;
    Why did you declared curr as a pointer to pointer? It could be just a regular pointer, couldn't it?

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    928
    No. If curr could just be a single-level pointer I would've wrote it that way since it would be simpler. The reason you need the second level of indirection is that we don't want curr to hold the value of a pointer, but instead to hold the address of where that value is stored.

    By storing the address where the pointer value is stored we can write to that address by dereferencing curr, modifying the value (which itself happens to be a pointer) at that address. It is this ability that allows us to eliminate some of the repetitive code in your attempt. The way you did it, there is a fundamental difference between "head" and all of the "next" pointers, and you need separate code to deal with that difference. But by using another level of indirection and pointing to the place where the pointers are stored, the "head" storage location and the "next" storage locations all look the same and can be handled by the same piece of code.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    This is similar to john.c's answer, but only checks for a == NULL or b == NULL as needed, instead of a while that checks both for every node moved.

    Code:
    ListNode * MergeLists(ListNode *a, ListNode *b)
    {
    ListNode *head;
    ListNode **curr = &head;
        if(a == NULL)                       /* if either list empty, */
            return b;                       /*  return the other */
        if(b == NULL)
            return a;
        while(1){                           /* merge the lists */
            if(a->data <= b->data){
                *curr = a;
                curr = &(a->next);
                a = *curr;
                if(a == NULL){
                    *curr = b;
                    break;}}
            else{
                *curr = b;
                curr = &(b->next);
                b = *curr;
                if(b == NULL){
                    *curr = a;
                    break;}}}
        return head;
    }
    Last edited by rcgldr; 03-24-2020 at 05:26 AM.

  7. #7
    Registered User
    Join Date
    Mar 2020
    Posts
    10
    I discover how to use dummy nodes whose .next element points to the beginning of a list.
    This is how I defined merge:

    Code:
    struct listnode *
    merge(struct listnode *a, struct listnode *b)
    {
        struct listnode head;
        struct listnode *p;
    
        head.next = NULL;
        p = &head;
        while (a != NULL && b != NULL) {
            if (a->data <= b->data) {
                p->next = a;
                a = a->next;
            } else {
                p->next = b;
                b = b->next;
            }
            p = p->next;
        }
        if (a != NULL)
            p->next = a;
        if (b != NULL)
            p->next = b;
    
        return head.next;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. ordered linked list
    By redmondtab in forum C Programming
    Replies: 48
    Last Post: 10-22-2006, 06:09 AM
  2. problme with ordered linked list
    By palku in forum C Programming
    Replies: 5
    Last Post: 09-19-2005, 04:33 PM
  3. function linked lists help
    By revelation437 in forum C++ Programming
    Replies: 4
    Last Post: 05-08-2003, 12:42 PM
  4. Insert Function For Linked Lists?
    By Daniel in forum C++ Programming
    Replies: 2
    Last Post: 02-02-2003, 06:07 PM

Tags for this Thread