Problems with liked list

[Wwx95]

Can anyone help to explain how is the class Solution compile?
I tried to understand as below:
First judge if head is null,for the first time call this function,head is null,so build a new node,then second time call,now the head is not null,so set a node whose name is curr,point to where head point,then where is

curr->next

point to?Anyway,it is not null,right?So we set curr point to where

curr->next

point to,then build a new node?I am confused in here.Thanks,I want to draw a figure to show this process,but I don't know where should I put these data: curr, curr->next.... Thanks.

#include <iostream>
#include <cstddef>
using namespace std;	
class Node
{
    public:
        int data;
        Node *next;
        Node(int d){
            data=d;
            next=NULL;
        }
};
class Solution{
    public:        
        Node* insert(Node *head,int data)
      {
        if (head == NULL)
        {
            head = new Node(data);
        }
        else
        {
            Node *curr = head;
            while (curr->next != NULL)
                curr = curr->next;
            
            curr->next = new Node(data);
        }
        
        return head;
      }
void display(Node *head)
      {
          Node *start=head;
          while(start)
          {
              cout<<start->data<<" ";
              start=start->next;
          }
      }
};

int main()
{
	Node* head=NULL;
  	Solution mylist;
    int T,data;
    cin>>T;
    while(T-->0){
        cin>>data;
        head=mylist.insert(head,data);
    }	
	mylist.display(head);
		
}

Insert function should return a reference to the node of the linked list.

Sample Input
The first line contains T, the number of test cases.
The subsequent lines of test cases each contain an integer to be inserted at the list's tail.
4
2
3
4
1

Sample Output
Prints the ordered data values for each element in your list as a single line of space-separated integers:

2 3 4 1

[2kaud]

Usually head would be a member of Solution then .insert() and .display() then doesn't require head as a parameter. When my VS has finished installing update 3 I'll post some example code.

[2kaud]

Consider

#include <iostream>
using namespace std;

class Node
{
private:
	int data;
	Node *next;

public:
	Node(int d) : data(d), next(nullptr) {}

	Node* getNext() const
	{
		return next;
	}

	void setNext(Node* const n)
	{
		next = n;
	}

	int getData() const
	{
		return data;
	}
};

class Solution
{
private:
	Node* head = nullptr;

public:
	void insert(int data)
	{
		if (head == nullptr)
			head = new Node(data);
		else
		{
			Node *curr = head;
			while (curr->getNext() != nullptr)
				curr = curr->getNext();

			curr->setNext(new Node(data));
		}

		return;
	}

	void display() const
	{
		for (Node* start = head; start; start = start->getNext())
			cout << start->getData() << " ";
	}
};

int main()
{
	Solution mylist;
	int T, data;
	cin >> T;

	while (T--)
	{
		cin >> data;
		mylist.insert(data);
	}

	mylist.display();
}

First note that the class Solution doesn't have a destructor which it should have to free the allocated memory for the list.

This is a single forward linked list where each node points to the following node in the list. Nodes are added at the end of the list. A node consists of the data and a pointer to the memory address of the next node in the linked list. If there is no next node (ie it is the end node of the list) then the next node is nullptr. There is a pointer called head that points to the first node in the linked list. If the linked list is empty then head will be nullptr.

At first, the linked list is empty so head is nullptr. When a node is added to the list, head is nullptr is head is set to point to the first allocated node of the list. If head is not nullptr when a node is added then this means that there is already at least one node in the linked list. Therefore to add a new node at the end of the list the last node in the list needs to be determined. So the code loops through all the nodes from the one pointed to by head by following the link to the next node until the next link is nullptr. At this point we have the last node in the linked list. This next element of the last node is then set to point to the newly allocated node.

Adding a new node at the end this way is expensive as for each insertion the end of the list has to be found. A better way is to main a pointer that points to the end node of the list (similar to how head points to the start of the list). This way an insertion can be done immediately without having to first traverse the list.

[Wwx95]

Consider

#include <iostream>
using namespace std;

class Node
{
private:
	int data;
	Node *next;

public:
	Node(int d) : data(d), next(nullptr) {}

	Node* getNext() const
	{
		return next;
	}

	void setNext(Node* const n)
	{
		next = n;
	}

	int getData() const
	{
		return data;
	}
};

class Solution
{
private:
	Node* head = nullptr;

public:
	void insert(int data)
	{
		if (head == nullptr)
			head = new Node(data);
		else
		{
			Node *curr = head;
			while (curr->getNext() != nullptr)
				curr = curr->getNext();

			curr->setNext(new Node(data));
		}

		return;
	}

	void display() const
	{
		for (Node* start = head; start; start = start->getNext())
			cout << start->getData() << " ";
	}
};

int main()
{
	Solution mylist;
	int T, data;
	cin >> T;

	while (T--)
	{
		cin >> data;
		mylist.insert(data);
	}

	mylist.display();
}

First note that the class Solution doesn't have a destructor which it should have to free the allocated memory for the list.

This is a single forward linked list where each node points to the following node in the list. Nodes are added at the end of the list. A node consists of the data and a pointer to the memory address of the next node in the linked list. If there is no next node (ie it is the end node of the list) then the next node is nullptr. There is a pointer called head that points to the first node in the linked list. If the linked list is empty then head will be nullptr.

At first, the linked list is empty so head is nullptr. When a node is added to the list, head is nullptr is head is set to point to the first allocated node of the list. If head is not nullptr when a node is added then this means that there is already at least one node in the linked list. Therefore to add a new node at the end of the list the last node in the list needs to be determined. So the code loops through all the nodes from the one pointed to by head by following the link to the next node until the next link is nullptr. At this point we have the last node in the linked list. This next element of the last node is then set to point to the newly allocated node.

Adding a new node at the end this way is expensive as for each insertion the end of the list has to be found. A better way is to main a pointer that points to the end node of the list (similar to how head points to the start of the list). This way an insertion can be done immediately without having to first traverse the list.

But my problem is that when the head is not null,then according to the .insert function,we set a curr pointer points to where head points,right?So what is curr->next now? Because we I need to judge if it is null, then if it is not null, by " curr = curr->getNext(); " ,we make curr points to where curr->next points to,am I right?

[2kaud]

we set a curr pointer points to where head points,right

Yes.

So what is curr->next now

This points to the address of the next node in the list, or nullptr if there is no next node.

if it is not null, by " curr = curr->getNext(); " ,we make curr points to where curr->next points to

Yes.