Insertion at the Kth position of LL

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

Given the head of a singly linked list and two integers X and K, insert a node with value X as the k^th node of the linked list and return the head of the modified list.

Examples:

Input: head -> 1 -> 2 -> 3, X = 5, K = 2

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

Input: head, X = 7, K = 1

Output: head -> 7

Explanation: Note that the value of the head was changed.

Input: head -> 1 -> 2, X = 15, K = 3

Constraints

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

Hints

Traverse the list to find the (K−1)-th node (the node just before the desired position). Create a new node with value X.
Use a pointer to traverse the list, keeping track of the current position. Stop when you reach the (K−1)-th node or when the list ends.

Company Tags

Splunk Instacart NVIDIA Robinhood Twilio Roblox Etsy Docker Wayfair AMD McKinsey & Company Philips Healthcare HashiCorp Chewy Pinterest MongoDB Flipkart Ubisoft Western Digital Bungie Riot Games Goldman Sachs Lyft eBay Stripe TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

The intuition is to traverse the linked list up to the position just before the desired insertion point. Once there, create a new node with the given value and update the links so that the new node is inserted at the correct position. This involves pointing the new node to the subsequent node and updating the previous node to point to the new node.

Approach:

Initialize a temporary pointer to traverse the list and a counter variable to track the number of nodes traversed.
Move the pointer until you reach the node just before the desired insertion position (k-1).
Create the new node with the given value.
To insert the new node:
- Set the new node's next pointer to the current (k)th node (temp->next).
- Update the (k-1)th node's next pointer to the new node, completing the insertion.
If the traversal finishes before reaching the (k-1)th node, it means k is larger than the length of the list plus one, so no node will be inserted.

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 kth position 
    ListNode* insertAtKthPosition(ListNode* &head, int X, int K) {
       /* If the linked list is empty 
       and k is 1, insert the 
       new node as the head*/
        if (head == NULL) {
            if (K == 1)
                return new ListNode(X);
            else
                return head;
        }
    
        /*If K is 1, insert the new
         node at the beginning 
         of the linked list*/
        if (K == 1)
            return new ListNode(X, head);
    
        int cnt = 0;
        ListNode* temp = head;
    
       /* Traverse the linked list 
       to find the node at position k-1*/
        while (temp != NULL) {
            cnt++;
            if (cnt == K-1) {
               /* Insert the new node after the node 
               at position k-1*/
                ListNode* newNode = new ListNode(X, temp->next);
                temp->next = newNode;
                break;
            }
            temp = temp->next;
        }
    
        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, 30, 40};
    int X = 20, K = 2;
    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.insertAtKthPosition(head, X, K);

    // Print the modified linked list
    cout << "List after inserting the given value at the Kth position: ";
    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 kth position 
    public ListNode insertAtKthPosition(ListNode head, int X, int K) {
        /* If the linked list is empty 
        and k is 1, insert the 
        new node as the head */
        if (head == null) {
            if (K == 1)
                return new ListNode(X);
            else
                return head;
        }

        /* If K is 1, insert the new
        node at the beginning 
        of the linked list */
        if (K == 1)
            return new ListNode(X, head);

        int cnt = 0;
        ListNode temp = head;

        /* Traverse the linked list 
        to find the node at position k-1 */
        while (temp != null) {
            cnt++;
            if (cnt == K - 1) {
                /* Insert the new node after the node 
                at position k-1 */
                ListNode newNode = new ListNode(X, temp.next);
                temp.next = newNode;
                break;
            }
            temp = temp.next;
        }

        return head;
    }
}

// Main class
class Main {
    // Helper Method 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();
    }
    
    // main method
    public static void main(String[] args) {
        // Create a linked list from an array
        int[] arr = {10, 30, 40};
        int X = 20, K = 2;
        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.insertAtKthPosition(head, X, K);

        // Print the modified linked list
        System.out.print("List after inserting the given value at the Kth position: ");
        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 kth position 
    def insertAtKthPosition(self, head, X, K):
        ''' If the linked list is empty 
        and k is 1, insert the 
        new node as the head '''
        if head is None:
            if K == 1:
                return ListNode(X)
            else:
                return head
        
        ''' If K is 1, insert the new
        node at the beginning 
        of the linked list '''
        if K == 1:
            return ListNode(X, head)
        
        cnt = 0
        temp = head

        ''' Traverse the linked list 
        to find the node at position k-1 '''
        while temp is not None:
            cnt += 1
            if cnt == K - 1:
                ''' Insert the new node after the node 
                at position k-1 '''
                newNode = ListNode(X, temp.next)
                temp.next = newNode
                break
            temp = temp.next
        
        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, 30, 40]
    X = 20
    K = 2
    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.insertAtKthPosition(head, X, K)

    # Print the modified linked list
    print("List after inserting the given value at the Kth position: ", 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 kth position 
    insertAtKthPosition(head, X, K) {
        /* If the linked list is empty 
        and k is 1, insert the 
        new node as the head */
        if (head === null) {
            if (K === 1)
                return new ListNode(X);
            else
                return head;
        }

        /* If K is 1, insert the new
        node at the beginning 
        of the linked list */
        if (K === 1)
            return new ListNode(X, head);

        let cnt = 0;
        let temp = head;

        /* Traverse the linked list 
        to find the node at position k-1 */
        while (temp !== null) {
            cnt++;
            if (cnt === K - 1) {
                /* Insert the new node after the node 
                at position k-1 */
                let newNode = new ListNode(X, temp.next);
                temp.next = newNode;
                break;
            }
            temp = temp.next;
        }

        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, 30, 40];
let X = 20, K = 2;
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.insertAtKthPosition(head, X, K);

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

Complexity Analysis:

Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head. Space Complexity: O(1) no extra space used.

Frequently Occurring Doubts

Q: What if K is greater than the length of the list + 1?

A: Append the new node at the tail. Traverse to the end of the list and update the last node’s next pointer to point to the new node.

Q: How do you ensure the list structure remains intact?

A: By carefully updating the next pointers of the surrounding nodes during insertion, you maintain the integrity of the linked list.

Interview Followup Questions

Q: How would you handle circular linked lists?

A: For circular linked lists: Traverse the list to the (K−1)-th node. Insert the new node and update pointers to maintain the circular structure.

Q: What if the list is sorted?

A: If the list is sorted, traverse the list to find the correct position based on X’s value and insert the new node there.

Notes

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

Problem Categories