Insertion at the tail of LL

Linked-List Fundamentals (Single LL) Easy Go Ad-Free - ₹20/mo

Given the head of a singly linked list and an integer X, insert a node with value X at the tail of the linked list and return the head of the modified list.

The tail is the last node of the linked list.

Examples:

Input: head -> 1 -> 2 -> 3, X = 7

Output: head -> 1 -> 2 -> 3 -> 7

Explanation: 7 was added as the last node.

Input: head, X = 0

Output: head -> 0

Explanation: 0 was added as the last/only node.

Input: head -> 5 -> 6, X = 8

Constraints

0 <= number of nodes in the Linked List <= 1000
0 <= ListNode.val <= 100
0 <= X <= 100

Hints

Create a new node with value X and set its next pointer to None. If the list is empty (head is None), the new node becomes the head of the list. Otherwise, traverse the list to reach the current tail (node whose next pointer is None).
Use a pointer to traverse the list starting from the head. Stop when the pointer reaches the tail node (where next is None). Update the next pointer of the tail node to point to the new node.

Company Tags

GE Healthcare Square Teladoc Health Flipkart Pinterest Texas Instruments Nutanix Robinhood Western Digital Medtronic Siemens Healthineers Roche Bloomberg KPMG OYO Rooms Twilio Target Mastercard DoorDash Deloitte Epic Games Databricks Walmart PwC Uber TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Traverse the list to the last node, then set it's next to the new node. If the list is empty, set the head to the new node.

Approach:

Create a new node with the given value and set its next to NULL.
Initialize a temporary pointer to the head to traverse the linked list.
Traverse the list using the temporary pointer until you reach the last node.
Point the next of the last node to the newly created node, making it the new tail of the linked list.
Return the head of the linked list to get the updated linked list.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

// Solution class
class Solution {
public:
    // Function to insert a new node at the tail of the linked list
    ListNode* insertAtTail(ListNode* &head, int X) {
        if (head == NULL)
            return new ListNode(X);

        ListNode* temp = head;
        // Traversing until the last node
        while (temp->next != NULL) {
            temp = temp->next;
        }
        
        ListNode* newNode = new ListNode(X);
        temp->next = newNode;

        return head;
    }
};

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list from a vector
    vector<int> arr = {10, 20, 30};
    int val = 40;
    ListNode* head = new ListNode(arr[0]);
    head->next = new ListNode(arr[1]);
    head->next->next = new ListNode(arr[2]);
    
    // Print the original list
    cout << "Original List: ";
    printLL(head);
    
    // Create a Solution object 
    Solution sol;
    head = sol.insertAtTail(head, val);

    // Print the modified linked list
    cout << "List after inserting the given value at the tail:";
    printLL(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;

    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

// Solution class
class Solution {
    // Function to insert a new node at the tail of the linked list
    public ListNode insertAtTail(ListNode head, int X) {
        if (head == null)
            return new ListNode(X);

        ListNode temp = head;
        // Traversing until the last node
        while (temp.next != null) {
            temp = temp.next;
        }

        ListNode newNode = new ListNode(X);
        temp.next = newNode;

        return head;
    }
}

// Main class
class Main {
    // Helper Function to print the linked list
    private static void printLL(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a linked list from an array
        int[] arr = {10, 20, 30};
        int val = 40;
        ListNode head = new ListNode(arr[0]);
        head.next = new ListNode(arr[1]);
        head.next.next = new ListNode(arr[2]);

        // Print the original list
        System.out.print("Original List: ");
        printLL(head);

        // Create a Solution object
        Solution sol = new Solution();
        head = sol.insertAtTail(head, val);

        // Print the modified linked list
        System.out.print("List after inserting the given value at the tail: ");
        printLL(head);
    }
}
# Definition of singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to insert a new node at the tail of the linked list
    def insertAtTail(self, head, X):
        if head is None:
            return ListNode(X)

        temp = head
        # Traversing until the last node
        while temp.next is not None:
            temp = temp.next

        newNode = ListNode(X)
        temp.next = newNode

        return head

# Helper Function to print the linked list
def printLL(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Create a linked list from a list
    arr = [10, 20, 30]
    val = 40
    head = ListNode(arr[0])
    head.next = ListNode(arr[1])
    head.next.next = ListNode(arr[2])

    # Print the original list
    print("Original List: ", end="")
    printLL(head)

    # Create a Solution object
    sol = Solution()
    head = sol.insertAtTail(head, val)

    # Print the modified linked list
    print("List after inserting the given value at the tail: ", end="")
    printLL(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

// Solution class
class Solution {
    // Function to insert a new node at the tail of the linked list
    insertAtTail(head, X) {
        if (head === null)
            return new ListNode(X);

        let temp = head;
        // Traversing until the last node
        while (temp.next !== null) {
            temp = temp.next;
        }

        let newNode = new ListNode(X);
        temp.next = newNode;

        return head;
    }
}

// Helper Function to print the linked list
function printLL(head) {
    let current = head;
    while (current !== null) {
        process.stdout.write(current.val + " ");
        current = current.next;
    }
    console.log();
}

// Main function
let arr = [10, 20, 30];
let val = 40;
let head = new ListNode(arr[0]);
head.next = new ListNode(arr[1]);
head.next.next = new ListNode(arr[2]);

// Print the original list
console.log("Original List: ");
printLL(head);

// Create a Solution object
let sol = new Solution();
head = sol.insertAtTail(head, val);

// Print the modified linked list
console.log("List after inserting the given value at the tail:");
printLL(head);

Complexity Analysis:

Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail. Here N is the length of the Linked List. Space Complexity: O(1) as no extra space used.

Frequently Occurring Doubts

Q: What is the difference between inserting at the tail and other positions?

A: Inserting at the tail requires traversal to the end of the list (unless the tail is tracked separately), while inserting at other positions might require locating a specific index or node.

Q: How do you ensure the new node is added at the correct position?

A: By traversing the list until the tail (node with next = None) is found and updating its next pointer to point to the new node.

Interview Followup Questions

Q: What if you frequently need to insert at the tail?

A: Maintain a direct reference to the tail node, allowing O(1) insertion without requiring traversal.

Q: What if the list needs to remain sorted after insertion?

A: Traverse the list to find the correct position based on X’s value, and insert the new node at that position.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories