Solution: Insertion at Tail

Let’s solve the Insertion at Tail problem.

We'll cover the following

Statement

Given the head of a linked list and a target, value, return the updated linked list head after adding the target value at the end of the linked list.

Constraints:

Let n be the number of nodes in the linked list:

  • 0≤0 \leq n ≤5×102\leq 5 \times 10^2

  • −5×103≤-5 \times 10^3 \leq node.data, value ≤5×103\leq 5 \times 10^3

Solution

To append a new node at the end of the linked list, we iterate the linked list until the last node is reached. After reaching the last node, we link the last node with the new node value so that the last node’s next pointer is pointing to the new node, and the new node’s next pointer is pointing to the NULL.

Here’s a breakdown of the steps involved in this solution:

  1. We create a new node containing the target, value.

  2. We check if the linked list’s head is NULL, indicating the list is empty. If TRUE, we set the new node as the head of the linked list.

  3. Otherwise, we initialize a temporary pointer, current, with the head of the linked list.

  4. Next, we iterate through the linked list until current.next is not NULL.

    1. For each node encountered, we move the current pointer to the next node.

  5. Once the last node is found, we link its next pointer to the new node, effectively appending the new node to the end of the linked list.

Let’s have a look at the following illustration for a better understanding of the algorithm above:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.