Given a pointer to the head of a linked list, write a method to insert a new node at end of the linked list. The head of the linked list could also be NULL i.e the linked list could initially be empty.

Your method will have two arguments - pointer to the head of linked list, and an integer to be inserted. Signature of the method should be - "Node* Insert(Node *head,int data)"

Your method should return back pointer to the head of the linked-list.

Since we need to return the head of the linked list, we store the initial head of the list in a seperate varible (here "org_list").

We allocate memory to a variable of type Node using malloc statement and assign the given data to the 'data' variable of the current new node and assign the 'next' pointer of the current new node to NULL

Now, we have 2 separate cases to handle:

1. If the head is initially NULL, then directly return the new created node (new_tail) as the head of a linked list with only one node.
2. If the head is initially not NULL, we reach the last node of the list using simple iteration. Then we assign the 'next' pointer of the last node to the new node that we created before. Then we return the initial head that we have stored earlier.

editorial written by i_coder

/*
  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)
{
    // Store the initial head of the list
    Node *org_head = head;
    //Declare a new variable of type Node using malloc statement
    Node *new_tail = (Node*) malloc(sizeof(Node));
    //Assign the given data to the current new node
    new_tail -> data = data;
    // Assign the 'next' pointer of the current new node to NULL
    new_tail -> next = NULL;
    // If the head is initially NULL, then directly 
    // return the new created node (new_tail) as the 
    // head of a linked list with only one node
    if(head == NULL)
    {
        return new_tail;
    }
    // While we do not reach the last node, move 
    // to the next node
    while(head -> next != NULL)
        head = head -> next;
    // Assign the 'next' pointer of the current 
    //node to the new_tail
    head->next = new_tail;
    //return the original head that we have 
    //stored separately before
    return org_head;
}

featured solution by i_coder