CODEWITHSUNDEEP
calgorithmmergelinked-listmergesort
R1451
R1451

Reputation: 11

Returning pointer to local variable sorted merge

In class I learned not to return pointers to local variables. In this function I found, sorted merge, it seems to return a pointer to a node. How come this is okay?

struct node *SortedMerge(struct node *a, struct node *b) { 
    struct node dummy; // a dummy first node to hang the result on
    
    struct node *tail = &dummy; // Points to the last result node --
                                // so tail->next is the place to add
                                // new nodes to the result.
    dummy.next = NULL;

    while (1) {
        if (a == NULL) { // if either list runs out, use the other list
            tail->next = b;
            break;
        } else
        if (b == NULL) {
            tail->next = a;
            break;
        }
        if (a->data <= b->data) {
            MoveNode(&(tail->next), &a);
        } else {
            MoveNode(&(tail->next), &b);
        }
        tail = tail->next;
    } //end while
    return (dummy.next);
}

void MoveNode(struct node **destRef, struct node **sourceRef) {
    struct node *newNode = *sourceRef;  // the front source node
    assert(newNode != NULL);
    *sourceRef = newNode->next;  // Advance the source pointer
    newNode->next = *destRef;    // Link the old dest off the new node
    *destRef = newNode;          // Move dest to point to the new node
}

Upvotes: 1

Views: 63

Answers (2)

chqrlie
chqrlie

Reputation: 144695

The function does not return a pointer to a local object, it returns the value of a local object dummy.next, a pointer initialized to NULL and set to either a or b during first iteration of the loop, depending on the values of a, b and the comparison of a->data and b->data if neither a nor b is a null argument.

The function uses a dummy list node to avoid making a special case of the first iteration. Here is a simpler version that uses a double pointer for the same purpose:

struct node *SortedMerge(struct node *a, struct node *b) {
    struct node *head = NULL;    // the head of the merged list.
    struct node **link = &head;  // pointer to the link to attach the next node to

    for (;;) {
        if (a == NULL) { // if either list runs out, use the other list
            *link = b;
            break;
        } else
        if (b == NULL) {
            *link = a;
            break;
        }
        if (a->data <= b->data) {
            *link = a;
            link = &a->next;
            a = a->next;
        } else {
            *link = b;
            link = &b->next;
            b = b->next;
        }
    }
    return head;
}

Here is a longer but arguably more readable version without double pointers:

struct node *SortedMerge(struct node *a, struct node *b) {
    struct node *head;    // the head of the merged list.
    struct node *tail;    // the tail node of the merged list.

    if (a == NULL)
        return b;
    if (b == NULL)
        return a;
    if (a->data <= b->data) {
        tail = head = a;
        a = a->next;
    } else {
        tail = head = b;
        b = b->next;
    }
    for (;;) {
        if (a == NULL) { // if either list runs out, use the other list
            tail->next = b;
            break;
        } else
        if (b == NULL) {
            tail->next = a;
            break;
        }
        if (a->data <= b->data) {
            tail = tail->next = a;
            a = a->next;
        } else {
            tail = tail->next = b;
            b = b->next;
        }
    }
    return head;
}

Upvotes: 0

Outrageous Bacon
Outrageous Bacon

Reputation: 562

You are correct that dummy is a local variable, and you should be concerned that a pointer to this local does not get returned. However, notice that what is returned is dummy.next, which is a pointer that could point to anything, so it's not forced to point to anything local.

Looking at the logic flow, dummy.next ends up pointing to either NULL, something related to input parameter a, or something related to input parameter b. That is, the returned pointer points to something related to the arguments, not the local structure.

By the way, the function's author was trying to help point that out by calling the local dummy. This is supposed to connote that it is not a real node (hence a dummy) that serves only as a convenient mechanism to process the function's logic and not a persistent node.

Upvotes: 4

Related Questions