Weird behavior on passing pointer by reference !!

[kapil2905]

Hello ppl :),

I am not sure if this is some pitfall when passing pointer by reference.
Kindly help me understand this behavior.

The question is to print the value of 1st & nth (last) node together in 1st line, 2nd & (n-1)st node in 2nd line and so on.

Eg. :
i/p :
1->2->3->4

o/p
1 4
2 3

i/p :
1->2->3->4->5

o/p :
1 5
2 4
(note that mid element is not printed if n is odd)


I wrote the following code for above problem :

Logic is
1) use two pointers (p,q) and userecusrsion and take one pointer to the end.
2) then start printing values p & q.
3) p = p->next, when the recursion stack unwinds, q will be one link back
as it is passed by value and p will be one link forwarded as it is passed
by reference.
4) return if (p == q) or (p->next == q)

/*struct Node
{
    int data;
    struct Node* next;
};*/

void ListDisplayHelper(Node *&p, Node *q) //p is received by ref., q by value
{
    if (!p || !q)   return;    //return if p or q is nullptr

    ListDisplayHelper(p, q->next);  //take q to the end recursively
    
    if (p == q) return;      //return from centre node if n is odd
    
    std::cout << p->data << " :  " << q->data << std::endl; 
    //print the i and n-i node.
    
    if (p->next == q)   return;  // return if centre reached for even n case.
    
    p = p->next;  //since p is received by reference, doing this operation
                  //should proceed p to next node and the same should be 
                  //visible in other recursion calls (or the behavior is
                  //different, not sure if what I am thinking is correct or 
                  //not :( ??)
}

void ListDisplay(struct Node *head)  //caller function, head = start of list
{
    auto *p{head}, *q{head};
    
    ListDisplayHelper(p, q);    
    
    return head;
}

for i/p :
10->20->30->40->50

above code o/p:
50 : 10 // correct is : 10 : 50
40 : 20 // correct is : 20 : 40
30 : 40 // and program should stop and not print last two lines.
20 : 50

Thanks in advance for help :)

[tpb]

It's your code that's "weird", not the behavior. :-) In particular you need a way to stop the second half of the code (post recursive call) from running after the pointers have met.

#include <iostream>
#include <cstdlib>

struct Node {
    int data;
    Node* next;    
    Node(int data, Node* next) : data(data), next(next) {}
};

bool ListDisplayHelper(const Node*& p, const Node* q) {
    if (!q) return true;
    if (!ListDisplayHelper(p, q->next) || p == q)
        return false;
    std::cout << p->data << " : " << q->data << '\n';
    p = p->next;
    return p != q;
}

void ListDisplay(const Node *head) {
    ListDisplayHelper(head, head);
}

int main(int argc, char **argv) {
    int high = 10;
    if (argc == 2) high = std::atoi(argv[1]);
    Node* head = nullptr;
    for (int i = 0; i < high; i++)
        head = new Node(i, head);
    ListDisplay(head);
}

Some comments on the recursive function:

bool ListDisplayHelper(const Node*& p, const Node* q) {

    // Once q hits the end of the list, return true
    // to signal that the post-recursion code should run.
    if (!q) return true;

    // Recurse q down to the end of the list.
    // If the return from the recursive call is false
    // then keep returning false so we pop all the way back up.
    // Also return false if the pointers have met.
    if (!ListDisplayHelper(p, q->next) || p == q)
        return false;

    std::cout << p->data << " : " << q->data << '\n';

    // Move the reference forward.
    p = p->next;

    // Return true if the pointers haven't met; false otherwise.
    return p != q;
}

[kapil2905]

Thanks alot tpb for explaining that post recusrion code was the actual issue :)