Problem Statement: Given a linked list and an integer value val, insert a new node with that value at the end (after the tail) of the list and return the updated linked list.
Examples
Example 1:
Input Format: 0->1->2 , val = 5
Result: 0->1->2->5
Explanation: We need to insert the value 5 after the tail of the given Linked List.
Example 2:
Input Format:12->5->8->7 , val = 100
Result: 12->5->8->7->100
Explanation: Again, we need to insert the value 100 after the tail of the Linked List.
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
To insert a new node after the tail of the linked list, create a new node pointing to NULL. This node will effectively be the new tail of the linked list. Traverse till the last node of the linked list and point it to the new node created to get the new tail of the linked list.
Algorithm:
Create a new node with data as the given value and pointing to the NULL. This node will be made our new tail of the linked list.
Initialize a temp pointer to the head that will be used to traverse the linked list.
Once it is iterated to the last node, point the tail to the new node created, making it the new tail of the linked list.
Return the head of the linked list to get the final updated linked list.
Code:
C++ Code
// Node class to represent a linked list node
class Node {
public:
int data;
Node* next;
// Constructor with both data and next node
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data (assuming next is initially null)
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to print the linked list
void printLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Function to insert a new node at the tail of the linked list
Node* insertTail(Node* head, int val) {
if (head == NULL)
return new Node(val);
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
Node* newNode = new Node(val);
temp->next = newNode;
return head;
}
int main() {
// Sample array and value for insertion
vector<int> arr = {12, 8, 5, 7};
int val = 100;
// Creating a linked list with initial elements from the array
Node* head = new Node(arr[0]);
head->next = new Node(arr[1]);
head->next->next = new Node(arr[2]);
head->next->next->next = new Node(arr[3]);
// Inserting a new node at the tail of the linked list
head = insertTail(head, val);
// Printing the linked list
printLL(head);
return 0;
}
Output:
12 8 5 7 100
Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.
Space Complexity: O(1), as we have not used any extra space.
Java Code
// Node class to represent a linked list node
class Node {
public int data;
public Node next;
// Constructor with both data and next node
public Node(int data1, Node next1) {
data = data1;
next = next1;
}
// Constructor with only data (assuming next is initially null)
public Node(int data1) {
data = data1;
next = null;
}
}
public class Main {
// Function to print the linked list
public static void printLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Function to insert a new node at the tail of the linked list
public static Node insertTail(Node head, int val) {
if (head == null)
return new Node(val);
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
Node newNode = new Node(val);
temp.next = newNode;
return head;
}
public static void main(String[] args) {
// Sample array and value for insertion
List<Integer> arr = Arrays.asList(12, 8, 5, 7);
int val = 100;
// Creating a linked list with initial elements from the array
Node head = new Node(arr.get(0));
head.next = new Node(arr.get(1));
head.next.next = new Node(arr.get(2));
head.next.next.next = new Node(arr.get(3));
// Inserting a new node at the tail of the linked list
head = insertTail(head, val);
// Printing the linked list
printLL(head);
}
}
Output:
12 8 5 7 100
Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.
Space Complexity: O(1), as we have not used any extra space.
Python Code
# Node class to represent a linked list node
class Node:
def __init__(self, data1, next1=None):
self.data = data1
self.next = next1
# Function to print the linked list
def printLL(head):
while head is not None:
print(head.data, end=" ")
head = head.next
# Function to insert a new node at the tail of the linked list
def insertTail(head, val):
if head is None:
return Node(val)
temp = head
while temp.next is not None:
temp = temp.next
new_node = Node(val)
temp.next = new_node
return head
if __name__ == "__main__":
# Sample array and value for insertion
arr = [12, 8, 5, 7]
val = 100
# Creating a linked list with initial elements from the array
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
head.next.next.next = Node(arr[3])
# Inserting a new node at the tail of the linked list
head = insertTail(head, val)
# Printing the linked list
printLL(head)
Output:
12 8 5 7 100
Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.
Space Complexity: O(1), as we have not used any extra space.
JavaScript Code
// Node class to represent a linked list node
class Node {
constructor(data1, next1 = null) {
this.data = data1;
this.next = next1;
}
}
// Function to print the linked list
function printLL(head) {
while (head !== null) {
console.log(head.data + " ");
head = head.next;
}
}
// Function to insert a new node at the tail of the linked list
function insertTail(head, val) {
if (head === null) {
return new Node(val);
}
let temp = head;
while (temp.next !== null) {
temp = temp.next;
}
const new_node = new Node(val);
temp.next = new_node;
return head;
}
// Sample array and value for insertion
const arr = [12, 8, 5, 7];
const val = 100;
// Creating a linked list with initial elements from the array
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
head.next.next.next = new Node(arr[3]);
// Inserting a new node at the tail of the linked list
head = insertTail(head, val);
// Printing the linked list
printLL(head);
Output:
12 8 5 7 100
Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.
Space Complexity: O(1), as we have not used any extra space.
In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.
Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article
