Given the head of a singly linked list, an integer value, and an integer k, insert a new node with the given value at the kth position using 1-based indexing and return the updated head.
Example 1
Input: head = [4, 8, 6, 3], value = 10, k = 3
Output: [4, 8, 10, 6, 3]
Explanation: Position 3 sits between value 8 and value 6, so the new node gets inserted between both nodes.
Example 2
Input: head = [9], value = 4, k = 2
Output: [9, 4]
Explanation: Position 2 matches the end of the linked list, so the new node gets attached after the old tail.
Approach
Insertion at a known linked list position becomes simple after the node just before the target position is reached. A new node only needs one link toward the old next node, and the previous node only needs one updated link toward the new node.
Algorithm
Create a new node with the given value, as this node will occupy the required position in the linked list.
If
k = 1, link the new node to the currentheadand return the new node, since inserting at the first position changes the head of the list.Initialize a traversal pointer at
head, as reaching the node just before positionkis enough to insert the new node.Move the pointer
k - 2times, which makes it stop at the node immediately before the required position.Store the current
nextnode in a temporary pointer, as this node should remain connected after the new node is inserted.Link the current node to the new node, making the new node part of the existing chain.
Link the new node to the temporary node, which preserves the remaining linked list after the insertion.
Return the original
head, since the first node remains unchanged whenkis greater than1.
Dry Run
insert at kth position
Solution
#include <bits/stdc++.h>using namespace std;struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {public: // Function to insert a new node at the kth position. Node* insertAtKthPosition(Node* head, int value, int k) { // Create a new node for the inserted value. Node* newNode = new Node(value); // Insert at head directly for position 1. if (k == 1) { newNode->next = head; return newNode; } // Start traversal from the head node. Node* current = head; // Move to the node before the kth position. for (int step = 1; step <= k - 2; step++) { current = current->next; } // Store the old next node before insertion. Node* nextNode = current->next; // Attach the new node after the current node. current->next = newNode; // Connect the remaining chain after the new node. newNode->next = nextNode; // Return the original head pointer. return head; }};// Function to create a linked list from an array.Node* createList(vector<int>& values) { // Return null for an empty input array. if (values.empty()) { return nullptr; } // Create the head node from the first value. Node* head = new Node(values[0]); Node* tail = head; // Append remaining values one by one. for (int index = 1; index < (int)values.size(); index++) { tail->next = new Node(values[index]); tail = tail->next; } return head;}// Function to print linked list values.void printList(Node* head) { // Start traversal from the head node. Node* current = head; // Print every node value in forward order. while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; } cout << "\n";}// Driver code.int main() { vector<int> values = {4, 8, 6, 3}; int value = 10; int k = 3; Node* head = createList(values); Solution sol; head = sol.insertAtKthPosition(head, value, k); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), traversal may move across the linked list until the node before the kth position appears.
Space Complexity: O(1), only one new node and a few pointer variables are used.
Interview follow-up Questions
Position 1 means head insertion, so the new node becomes the first node of the linked list.
Be the first to add a comment.