Problem Statement: Given a linked list, delete the tail of the linked list and print the updated linked list.
Examples
Example 1:
Examples:
Input Format: 0->1->2
Result: 0->1
Explanation: The tail of the list is the last node. After removing the tail, and updating the linked list, this result is what we get.
Example 2:
Input Format: 12->5->8->7
Result: 12->5->8
Explanation: Again, after deleting the tail and updating the linked list, the list ends at the second last node, which is the new tail.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
The main intuition is to point the second last node to null to get the updated linked list. Hence, we will iterate till the second last node and make it point to NULL. This will effectively skip the last node of the list therefore, we will free up the memory being occupied by this node (Only in the case of C++).
Two edge cases to consider are:
If the input linked list is empty, we return null.
If there is only one node in the list, that node itself will be the tail, therefore we return null after deleting that node.
Algorithm:
Start by initializing a pointer to the head of the list that will be used to iterate through the linked list. Iterate up to the second last node, this node will be our new tail of the list.
After reaching the second-to-last node, free up the memory occupied by the former tail or the last node of the list. Note: In the case of languages like Java, Python, and Javascript, there is no need for the deletion of objects or nodes because these have an automatic garbage collection mechanism that automatically identifies and reclaims memory that is no longer in use.
Finally, point the second last node or the new tail to NULL to obtain the updated linked list.
Code:
C++ Code
// Node class for a linked list
class Node {
public:
int data; // Data of the node
Node* next; // Pointer to the next node in the list
// Constructor for a node with both data and next node provided
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor for a node with only data provided, next initialized to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to print the linked list starting from the given head
void printLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Function to delete the tail node of a linked list and return the new head
Node* deleteTail(Node* head) {
// If the list is empty or has only one node, return NULL
if (head == NULL || head->next == NULL)
return NULL;
// Initialize a temporary pointer to traverse the list
Node* temp = head;
// Traverse to the second last node in the list
while (temp->next->next != NULL) {
temp = temp->next;
}
// Delete the last node
delete temp->next;
// Set the next of the second last node to nullptr, effectively removing the last node
temp->next = nullptr;
// Return the head of the modified list
return head;
}
int main() {
// Initialize a vector with values for the linked list
vector<int> arr = {12, 5, 8, 7};
// Create a linked list with the values from the vector
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]);
// Call the deleteTail function to delete the last node
head = deleteTail(head);
// Print the linked list after deletion
printLL(head);
}
Output: 12 5 8
Time Complexity: O(N) for traversing the linked list and updating the tail.
Space Complexity: O(1), as we have not used any extra space.
Java Code
// Node class definition
class Node {
int data;
Node next;
// Constructor with both data and next pointer
Node(int data1, Node next1) {
this.data = data1;
this.next = next1;
}
// Constructor with only data (next pointer set to null)
Node(int data1) {
this.data = data1;
this.next = null;
}
}
// LinkedList class
public class LinkedList {
// Function to delete the tail of the linked list
private static Node deleteTail(Node head) {
// Check if the linked list is empty or has only one node
if (head == null || head.next == null)
return null;
// Create a temporary pointer for traversal
Node temp = head;
// Traverse the list until the second-to-last node
while (temp.next.next != null) {
temp = temp.next;
}
// Nullify the connection from the second-to-last node to delete the last node
temp.next = null;
// Return the updated head of the linked list
return head;
}
// Function to print the linked list
private static void printLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Main method
public static void main(String[] args) {
// Initialize an array with integer values
int[] arr = {2, 5, 8, 7};
// Create the linked list with nodes initialized with array values
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]);
// Delete the tail of the linked list
head = deleteTail(head);
// Print the modified linked list
printLL(head);
}
}
Output: 12 5 8
Time Complexity: O(N) for traversing the linked list and updating the tail.
Space Complexity: O(1), as we have not used any extra space.
Python Code
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
# Function to delete the tail of the linked list
def delete_tail(head):
# Check if the linked list is empty or has only one node
if head is None or head.next is None:
return None
# Create a temporary pointer for traversal
temp = head
# Traverse the list until the second-to-last node
while temp.next.next is not None:
temp = temp.next
# Nullify the connection from the second-to-last node to delete the last node
temp.next = None
# Return the updated head of the linked list
return head
# Function to print the linked list
def print_ll(head):
while head is not None:
print(head.data, end=" ")
head = head.next
# Main function
if __name__ == "__main__":
# Initialize an array with integer values
arr = [2, 5, 8, 7]
# Create the linked list with nodes initialized with array values
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
head.next.next.next = Node(arr[3])
# Delete the tail of the linked list
head = delete_tail(head)
# Print the modified linked list
print_ll(head)
Output: 12 5 8
Time Complexity: O(N) for traversing the linked list and updating the tail.
Space Complexity: O(1), as we have not used any extra space.
JavaScript Code
// Node class definition
class Node {
constructor(data, nextNode = null) {
this.data = data;
this.next = nextNode;
}
// Function to delete the tail of the linked list
function deleteTail(head) {
// Check if the linked list is empty or has only one node
if (head === null || head.next === null) {
return null;
}
// Create a temporary pointer for traversal
let temp = head;
// Traverse the list until the second-to-last node
while (temp.next.next !== null) {
temp = temp.next;
}
// Nullify the connection from the second-to-last node to delete the last node
temp.next = null;
// Return the updated head of the linked list
return head;
}
// Function to print the linked list
function printLL(head) {
while (head !== null) {
console.log(head.data + " ");
head = head.next;
}
}
// Main function
function main() {
// Initialize an array with integer values
const arr = [2, 5, 8, 7];
// Create the linked list with nodes initialized with array values
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]);
// Delete the tail of the linked list
head = deleteTail(head);
// Print the modified linked list
printLL(head);
}
// Call the main function
main();
Output: 12 5 8
Time Complexity: O(N) for traversing the linked list and updating 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
