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:
n
node.data
,value
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:
We create a new node containing the target,
value
.We check if the linked list’s
head
is NULL, indicating the list is empty. If TRUE, we set the new node as thehead
of the linked list.Otherwise, we initialize a temporary pointer,
current
, with the head of the linked list.Next, we iterate through the linked list until
current->next
is not NULL.For each node encountered, we move the
current
pointer to the next node.
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 80+ hands-on prep courses.