Recursive function for Linked List (missing first value)

Hi there! I have been brushing up on Linked List as personal practice, and I have recently implemented a Linked List class in List.h as shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef LIST_H
#define LIST_H

class List
{
private: // can only be accessed by functions declared here
    
    typedef struct node
    {
        int data;
        node* next; //node pointer, purpose is to point to another node
        
    }* nodePtr;
    
    //typedef struct node* nodePtr; //type nodePtr, same as struct node*
    
    nodePtr head;
    nodePtr curr;
    nodePtr temp;
    
    
public: // This is where functions go
    List(); // Constructor, sets initial values of NodePtr
    void AddNode(int addData);
    void DeleteNode(int delData);
    void PrintList();
    void ReverseList();
    void callReverse();
    void ReverseRec(node* pointer);
    
    
};
#endif /* LIST_H */  


I have got the iterative way of reversing the Linked List correct, but when I tried to implement the recursive way, I am running into an issue where the initial head value is missing from my print function.

For example: 3 5 7 -> callReverse -> printList -> 7 5 (missing the 3)

Here is the code for my Linked List functions below:
The code in question is ReverseRec and callReverse (both required for recursive calls)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
<#include <iostream>
#include <cstdlib>

#include "List.h"

using namespace std;

List::List()
{
    head = NULL;
    curr = NULL;
    temp = NULL;
}

void List::AddNode(int addData)
{
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;
    
    //if list is already created(we have at least one elem in list)
    if(head != NULL) //can access privata data "head" because public function
    {
        curr = head;
        while(curr->next != NULL)
        {
            curr = curr->next;
        }
        curr->next = n;
    }
    
    else
    {
        head = n;
    }
}

void List::DeleteNode(int delData)
{
    nodePtr delPtr = NULL;
    temp = head;
    curr = head;
    while((curr != NULL) && curr->data != delData)
    {
        temp = curr;
        curr = curr->next;
    }
    if(curr == NULL) 
    {
        cout << "Data was not found.\n";
        delete delPtr;
    }
    
    else
    {
        delPtr = curr;
        curr = curr->next;
        temp->next = curr;
        delete delPtr;
        cout << "The value " << delData << " was deleted.\n";
    }
    
}

void List::PrintList()
{
    curr = head;
    while(curr != NULL)
    {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

void List::ReverseList()
{
    if(head == NULL) return;
    
    nodePtr prev = NULL;
    curr = head;
    while(curr != NULL)
    {
        temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    
    head = prev;
}

void List::callReverse(){
    
    nodePtr h = head;
    head = NULL;
    ReverseRec(h);
}

void List::ReverseRec(nodePtr pointer)
{
    if(pointer->next == NULL)
    {
        if(head == NULL)
            head = pointer;
    }
    else if(pointer->next->next!=NULL)
    {
        ReverseRec(pointer->next);
    }
    
    if(head == NULL)
    {
        head = pointer->next;
        pointer->next->next = pointer;
        pointer->next = NULL;
    }
} 


Any tips/advice would be appreciated! Thank you.

Here's the main.cpp as well if you were curious

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdlib>

#include <iostream>

#include "List.h"

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {

    List list;
    
    list.AddNode(3);
    list.AddNode(5);
    list.AddNode(7);
    list.callReverse();
    list.PrintList();
    
    return 0;
}
Last edited on
I think it could be something like this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void List::callReverse(){

    nodePtr h = head;
    head = nullptr;
    ReverseRec(h);
}

void List::ReverseRec(nodePtr pointer)
{
    nodePtr temp = new node;
    temp->data = pointer->data;    // copy the data
    temp->next = nullptr;          // prevent that we create a graph with a loop instead of a list
    if(pointer->next == nullptr)   // we found the tail node, this should be the first node to add to the reversed list
    {
        head = temp;                // add this node to the reversed list
        curr = head;                // and make it simple to add another node if there are more
    }
    else                            // this is not the first node to add to the reversed list
    {
        ReverseRec(pointer->next);  // it is this nodes turn when this function call returns
        curr->next = temp;          // finally add it
        curr = temp;                // and make it simple to add another node if there are more
    }
}
@OP,

I think if you take lines 114 and 115 and move them to after the curly brace on line 116 your program will work. The problem is, you are only adjusting the next pointers when head == NULL which won't be true at this point in the recursive call except for in the last recursion.
Topic archived. No new replies allowed.