C++

Forum

 
linked list

vikas choudhary (3)
this is the problem
https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list
and i tried
/*
Insert Node at the end of a linked list
head pointer input could be NULL as well for empty list
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
Node* Insert(Node *head,int data)
{
// Complete this method
Node *temp;
temp=head;
if(temp=='\0'){
temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=data;
head=temp;
head->next='\0';
}

else {
while (temp!='\0'){
temp=temp->next;
}
temp->data=data;
temp->next='\0';
}

return head;
}

but still not getting ouput
where i am wrong ??
gunnerfunner (2127)
Iterate through the list until you reach the last node:
1
2
3
4
5
 
	node* temp = head;
	do 
	{
		temp = temp -> next;
	} while (temp -> next != nullptr);

Now that you have reached the end, insert the new node into the list:
1
2
3
 
	node* s = new node;
	temp -> next = s;
	s -> next = nullptr;

And make sure you delete the pointers declared with new in the dtor or use smart pointers
vikas choudhary (3)
still not getting output
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
 

Node* Insert(Node *head,int data)
{
  // Complete this method
    Node* temp = head;
    
    if(temp==nullptr){
        temp=(struct Node *)malloc(sizeof(struct Node));
        temp->data=data;
        head=temp;
        head->next=nullptr;
    }
        
     else {        
	       do 
	       {
		      temp = temp -> next;
	       } while (temp -> next != nullptr);
         Node* s = new Node;
         s->data=data;
         s -> next = nullptr;
	     temp -> next = s;
delete(s);
         s=nullptr;

    }
    
    return head;
}
Last edited on
gunnerfunner (2127)
Yes because you deleted s right here and there is no other pointer to the object owned by s

edit: also, look at my earlier post: it's s->next = nullptr, not s = nullptr as you've done
Last edited on
vikas choudhary (3)
yes sir i tried in both ways i just removed both 23 and 24 statement but still not working .. and 23 24 i wrote because you said just delete created node so
i don't write these statement still not working

this is the problem

https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list

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
 
Node* Insert(Node *head,int data)
{
  // Complete this method
    Node* temp = head;
    
    if(temp==nullptr){
        temp=(struct Node *)malloc(sizeof(struct Node));
        head=temp;
        head->data=data;
        head->next=nullptr;
    }
        
     else {        
	       do 
	       {
		      temp = temp -> next;
	       } while (temp -> next != nullptr);
         Node* s = new Node;
         s -> data=data;
         s -> next = nullptr;
	     temp -> next = s;
    }
    
    return head;
}
Last edited on
gunnerfunner (2127)
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
#include <iostream>
#include <memory>
using std::cout;

struct node
{
    int info;
    std::shared_ptr<node> next;
};
struct single_llist
{
        std::shared_ptr<node> start;
        void create_list();
        void add_begin();
        void add_after();
        void insert_last_element();
        void display_dlist()const;
        double list_count()const;
        single_llist() : start (nullptr) {}
};
int main()
{
    int choice;
    single_llist sl;
    bool fQuit = false;
    while (!fQuit)
    {
        cout << "1. Create List \n2. Add at begining \n3. Add after position";
        cout << "\n4. Insert last element \n5. Display \n6. Count \n7. Quit \n";

        cout << "Enter your choice : \n";
        std::cin >> choice;
        switch ( choice )
        {
        case 1:
            sl.create_list();
            cout<< '\n';
            break;
        case 2:
            sl.add_begin();
            cout<< '\n';
            break;
        case 3:

            sl.add_after();
            cout << '\n';
            break;
        case 4:

            sl.insert_last_element();
            cout << '\n';
            break;
        case 5:
            sl.display_dlist();
            cout << '\n';
            break;
        case 6:
            cout << "List size: " << sl.list_count() << '\n';
            break;
        case 7:
            fQuit = true;
            break;
        default:
            cout << "Wrong choice\n";
            break;
        }
    }
    return 0;
}
void single_llist::create_list()
{
    if(this -> list_count() > 0)
    {
        cout << "List already created \n";
        return;
    }
    else
    {
        cout << "Enter the element: \n";
        double element;
        std::cin >> element;
        std::shared_ptr<node> temp (new node);
        temp->info = element;
        temp->next = nullptr;
        start = temp;
    }
}
void single_llist::add_begin()
{
    if (start == nullptr)
    {
        cout << "First Create the list.\n";
        return;
    }
    else
    {
        cout << "Enter the element: \n";
        double element;
        std::cin >> element;
        std::shared_ptr<node> temp(new node);
        temp->info = element;
        temp->next = start;
        start = temp;
        cout << "Element Inserted\n";
    }
}
void single_llist::add_after()
{
    if (start == nullptr)
    {
        cout << "First Create the list.\n";
        return;
    }
    else
    {
        cout << "Insert Element after postion (<= "<< this -> list_count() << " ): " ;
        double position;
        std::cin >> position;
        if ((position == 0) || (position > this->list_count()))
         {
            cout << "Position out of range \n";
            return;
         }
         else
         {
            cout << "Enter the element: \n";
            double element;
            std::cin >> element;
            std::shared_ptr<node> q = start;
            for (int i = 0; i < position - 1; i++)
            {
                q = q->next;
            }
            std::shared_ptr<node> tmp(new node);
            tmp->info = element;
            if (q->next == NULL)
            {
                q->next = tmp;
                tmp->next = NULL;
            }
            else
            {
                tmp->next = q->next;
                q->next = tmp;
            }
            cout << "Element Inserted \n";
         }
    }
}
void single_llist::insert_last_element()
{
    double element;
    if (this -> start == nullptr)
    {
         create_list();
        return;
    }
    else
    {
        cout << "Enter the element to insert: ";
        std::cin >> element;
        std::shared_ptr<node> tmp = start;
        do
        {
            tmp = tmp -> next;
        } while (tmp -> next != nullptr);

        std::shared_ptr<node> s (new node);
        tmp -> next = s;
        s -> info = element;
        s -> next = nullptr;

        return;
    }
}
void single_llist::display_dlist()const
{
    if (start == nullptr)
    {
        cout << "List empty,nothing to display \n";
        return;
    }
    std::shared_ptr<node> q = start;
    cout << "The Link List is : \n";
    while (q != nullptr)
    {
        cout << q->info << " <-> ";
        q = q->next;
    }
    cout<< "NULL \n";
}
double single_llist::list_count()const
{
    std::shared_ptr<node> q = start;
    double counter {};
    while (q != nullptr)
    {
        q = q->next;
        counter++;
    }
    return counter;
}
Last edited on
gunnerfunner (2127)
Better still, with template:
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
#include <iostream>
#include <memory>
using std::cout;

template <typename T>
struct node
{
    T info;
    std::shared_ptr<node<T>> next;
};
template <typename T>
struct single_llist
{
        std::shared_ptr<node<T>> start;
        void create_list();
        void add_begin();
        void add_after();
        void insert_last_element();
        void display_dlist()const;
        double list_count()const;
        single_llist() : start (nullptr) {}
};
int main()
{
    int choice;
    single_llist<int> sl;
    bool fQuit = false;
    while (!fQuit)
    {
        cout << "1. Create List \n2. Add at begining \n3. Add after position";
        cout << "\n4. Insert last element \n5. Display \n6. Count \n7. Quit \n";

        cout << "Enter your choice : \n";
        std::cin >> choice;
        switch ( choice )
        {
        case 1:
            sl.create_list();
            cout<< '\n';
            break;
        case 2:
            sl.add_begin();
            cout<< '\n';
            break;
        case 3:

            sl.add_after();
            cout << '\n';
            break;
        case 4:

            sl.insert_last_element();
            cout << '\n';
            break;
        case 5:
            sl.display_dlist();
            cout << '\n';
            break;
        case 6:
            cout << "List size: " << sl.list_count() << '\n';
            break;
        case 7:
            fQuit = true;
            break;
        default:
            cout << "Wrong choice\n";
            break;
        }
    }
    return 0;
}
template <typename T>
void single_llist<T>::create_list()
{
    if(this -> list_count() > 0)
    {
        cout << "List already created \n";
        return;
    }
    else
    {
        cout << "Enter the element: \n";
        T element;
        std::cin >> element; //overload operator >> as necessary
        std::shared_ptr<node<T>> temp (new node<T>);
        temp->info = element;
        temp->next = nullptr;
        start = temp;
    }
}
template <typename T>
void single_llist<T>::add_begin()
{
    if (start == nullptr)
    {
        cout << "First Create the list.\n";
        return;
    }
    else
    {
        cout << "Enter the element: \n";
        T element;
        std::cin >> element;
        std::shared_ptr<node<T>> temp(new node<T>);
        temp->info = element;
        temp->next = start;
        start = temp;
        cout << "Element Inserted\n";
    }
}
template <typename T>
void single_llist<T>::add_after()
{
    if (start == nullptr)
    {
        cout << "First Create the list.\n";
        return;
    }
    else
    {
        cout << "Insert Element after postion (<= "<< this -> list_count() << " ): " ;
        T position;
        std::cin >> position;
        if ((position == 0) || (position > this->list_count()))
         {
            cout << "Position out of range \n";
            return;
         }
         else
         {
            cout << "Enter the element: \n";
            T element;
            std::cin >> element;
            std::shared_ptr<node<T>> q = start;
            for (int i = 0; i < position - 1; i++)
            {
                q = q->next;
            }
            std::shared_ptr<node<T>> tmp(new node<T>);
            tmp->info = element;
            if (q->next == NULL)
            {
                q->next = tmp;
                tmp->next = NULL;
            }
            else
            {
                tmp->next = q->next;
                q->next = tmp;
            }
            cout << "Element Inserted \n";
         }
    }
}
template <typename T>
void single_llist<T>::insert_last_element()
{
    T element;
    if (this -> start == nullptr)
    {
         create_list();
        return;
    }
    else
    {
        cout << "Enter the element to insert: ";
        std::cin >> element;
        std::shared_ptr<node<T>> tmp = start;
        do
        {
            tmp = tmp -> next;
        } while (tmp -> next != nullptr);

        std::shared_ptr<node<T>> s (new node<T>);
        tmp -> next = s;
        s -> info = element;
        s -> next = nullptr;

        return;
    }
}
template <typename T>
void single_llist<T>::display_dlist()const
{
    if (this ->start == nullptr)
    {
        cout << "List empty,nothing to display \n";
        return;
    }
    std::shared_ptr<node<T>> q = start;
    cout << "The Link List is : \n";
    while (q != nullptr)
    {
        cout << q->info << " <-> ";//overload operator << as necessary 
        q = q->next;
    }
    cout<< "NULL \n";
}
template <typename T>
double single_llist<T>::list_count()const
{
    std::shared_ptr<node<T>> q = this -> start;
    double counter {};
    while (q != nullptr)
    {
        q = q->next;
        counter++;
    }
    return counter;
}
Last edited on
dhayden (5795)
gunnerfunner,
1
2
3
4
5
 
	node* temp = head;
	do 
	{
		temp = temp -> next;
	} while (temp -> next != nullptr);

This dereferences a null pointer at line 4 if the list is empty, and at line 5 if the list contains exactly one item.

Your other solution doesn't meet the requirements.

vikas choudhary, here's your first solution with code tags and indentation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
Node *
Insert(Node * head, int data)
{
// Complete this method
    Node *temp;
    temp = head;
    if (temp == '\0') {
        temp = (struct Node *) malloc(sizeof(struct Node));
        temp->data = data;
        head = temp;
        head->next = '\0';
    }

    else {
        while (temp != '\0') {
            temp = temp->next;
        }
        temp->data = data;
        temp->next = '\0';
    }

    return head;
}

The problem here is that line 18 derefences a null pointer.

Regarding your second attempt, gunnerfunner pointed out one bug (deleting s). In addition, that will fail if there is exactly one item in the list because line 16 (temp = temp->next) will assign a null pointer to temp and the next line will dereference it.

Here is a modified version of your first attempt that works:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
Node *
Insert(Node * head, int data)
{
    // Create the new node just once.
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
    } else {
        // Point temp to the last node
        Node *temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }

        // Now append the newNode
        temp->next = newNode;
    }

    return head;
}


But this is still a crappy way to insert into a linked list because it requires that you always call Insert with head = Insert(head, somevalue);. It makes much more sense to pass a reference to the head pointer (void Insert Node* &head, int data)).

If Insert() had that prototype then the code could be written without special cases by using a pointer-to-pointer. This points to either head, or the next member that points to the current node:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void
Insert(Node * &head, int data)
{
    // Create the new node just once.
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;

    Node **headOrNext = &head;
    while (*headOrNext) {
        headOrNext = &(*headOrNext)->next;
    }
    *headOrNext = newNode;
}

By the way, the same method works great when deleting nodes.
gunnerfunner (2127)
Your other solution doesn't meet the requirements.

Namely?
dhayden (5795)
Namely it doesn't even contain the method that must be written:
Node* Insert(Node* head, int data)

Full requirements here: https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list
gunnerfunner (2127)
It'd be trivial to edit any of the add functions to match given function signature
Last edited on
Topic archived. No new replies allowed.