CODEWITHSUNDEEP
c++linked-list
user6490375
user6490375

Reputation:

Pointer returns

I am solving a coding challenge. In this challenge, we would be given two linked lists (2 -> 4 -> 3) and (5 -> 6 -> 4) and we have to return the result of their addition (7 -> 0 -> 8).

While I did solve it, I found a better version on Google:

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode preHead(0), *p = &preHead;
    int extra = 0;
    while (l1 || l2 || extra) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
        extra = sum / 10;
        p->next = new ListNode(sum % 10);
        p = p->next;
        l1 = l1 ? l1->next : l1;
        l2 = l2 ? l2->next : l2;
    }
    return preHead.next;
}

However, I don't understand the step ListNode preHead(0), *p = &preHead;. The address of preHead is being stored in the pointer variable p. In other words, p points to preHead. Then, why is preHead.next being returned in the end? Note that this code does compile and return the expected output.

Appreciate your help!

Upvotes: 1

Views: 822

Answers (3)

txtechhelp
txtechhelp

Reputation: 6777

Then, why is preHead.next being returned in the end?

Because addTwoNumbers returns a pointer but preHead is a stack variable (i.e. a temporary); returning a temporary reference as a pointer to be de-referenced later is undefined behavior.

However, preHead.next is a heap allocated variable and can then be properly de-referenced when it needs to be.

Upvotes: 0

David G
David G

Reputation: 96810

I like to call it the Dummy Node Pattern. It's where the user will construct an unused node for the purpose of making things like insertion and lookup a lot easier to implement. As you can see in the function, p already points to a valid node to begin with, so there is no need to check if p is NULL and set it to a node of this is true, rather we just append a node using p->next. This is the alternative code where p's starting value is NULL:

ListNode* p = nullptr;
ListNode* tail;
while (l1 || l2 || extra) {
    //int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
    //extra = sum / 10;
    if (p != nullptr) {
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
    } else {
        tail = p = new ListNode(sum % 10);
    }
    //l1 = l1 ? l1->next : l1;
    //l2 = l2 ? l2->next : l2;
}
return p;

We would have to keep an extra pointer to the end of the list so we know where to insert at each iteration. And we have to make sure p is not a null pointer in the case of inserting for the first time.

The reason preHead.next is returned is because preHead.next is where the insertion begins (it is the head of the actual linked list we want to return).

Upvotes: 1

Mikel F
Mikel F

Reputation: 3671

The following line:

p->next =new ListNode(sum % 10);

Allocates the new node that is returned.

In the first iteration of the loop, *p is the same as preHead. Later iterations move p, but do not invalidate preHead holding a pointer to the first new element added.

Upvotes: 0

Related Questions