Given the head of a singly linked list, an integer value, and an integer X, insert a new node with the given value before the first node whose value equals X and return the updated head.
Example 1
Input: head = [4, 2, 7, 5], value = 10, X = 7
Output: [4, 2, 10, 7, 5]
Explanation: Value 7 appears in the third node, so the new node gets inserted between value 2 and value 7.
Example 2
Input: head = [9, 1, 3], value = 6, X = 9
Output: [6, 9, 1, 3]
Explanation: Value 9 appears at the head node, so the new node becomes the new head.
Approach 1
A direct method scans the linked list from left to right until value X appears. During traversal, one pointer tracks the current node and another pointer tracks the previous node, so insertion can reconnect the chain immediately before the matched node.
Algorithm
Create a new node with the given value, as this node will be inserted immediately before the node containing
X.If the head node stores value
X, link the new node to the currentheadand return the new node, since insertion before the head makes the new node the updated head.Initialize
previousasheadandcurrentashead.next, wherepreviouskeeps track of the node just beforecurrent.Traverse the linked list while
currentis notnull, as each node needs to be checked until the first occurrence ofXis found.If
current->dataequalsX, linkprevious->nextto the new node and the new node tocurrent, which places the new node immediately before the matched node.Return the original
headafter insertion, since the head remains unchanged whenXis not stored in the first node.If the traversal reaches the end without finding
X, return the originalhead, as no insertion position exists.
Dry Run
insert before value x
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 before the first node with value X. Node* insertBeforeValueX(Node* head, int value, int x) { // Create a new node for the inserted value. Node* newNode = new Node(value); // Return the original head after no node exists. if (head == nullptr) { delete newNode; return head; } // Insert at head directly after a head match. if (head->data == x) { newNode->next = head; return newNode; } // Start previous at head and current at the second node. Node* previous = head; Node* current = head->next; // Traverse until a matching value appears or the list ends. while (current != nullptr) { // Stop after finding the first matching node. if (current->data == x) { // Connect previous node to the new node. previous->next = newNode; // Connect the new node to the matched node. newNode->next = current; return head; } // Move both pointers one step forward. previous = current; current = current->next; } // Release the unused node after no match appears. delete newNode; // Return the original head after no match appears. 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 sequence. while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; } cout << "\n";}// Driver code.int main() { vector<int> values = {4, 2, 7, 5}; int value = 10; int x = 7; Node* head = createList(values); Solution sol; head = sol.insertBeforeValueX(head, value, x); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), traversal may visit every node once before finding value X or reaching list end.
Space Complexity: O(1), only two pointer variables and one new node are used.
Approach 2
The previous-pointer method requires separate handling when value X is present at the head. Adding a dummy node before the head removes this special case because every real node, including the head, has a previous node.
The traversal checks the next node for value X. When a match is found, the new node is inserted between the current node and the matched node. This allows head insertion and middle insertion to use the same pointer update logic.
Algorithm
Create a new node with the given value, as this node will be placed immediately before the node containing
X.Create a dummy node and connect it to the
head, as this gives every actual node, including the head, a previous node.Initialize a traversal pointer at the dummy node, so the next node can be checked for the target value.
Traverse while the next node exists and does not contain
X, as the pointer needs to stop at the node immediately before the first occurrence ofX.When the next node contains
X, link the current node to the new node and the new node to the matched node, which inserts the new node directly beforeX.Return
dummy.nextas the updated head, since it correctly represents the head whether the insertion happened before the original head or somewhere later in the list.
Dry Run
insert before x dummy
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 before the first node with value X. Node* insertBeforeValueX(Node* head, int value, int x) { // Create a new node for the inserted value. Node* newNode = new Node(value); // Create a dummy node before the real head node. Node dummy(0); dummy.next = head; // Start traversal from the dummy node. Node* current = &dummy; // Traverse while the next node exists. while (current->next != nullptr) { // Stop after finding the first matching next node. if (current->next->data == x) { // Connect the new node before the matched node. newNode->next = current->next; current->next = newNode; return dummy.next; } // Move one step forward in the list. current = current->next; } // Release the unused node after no match appears. delete newNode; // Return the updated head through dummy.next. return dummy.next; }};// 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 sequence. while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; } cout << "\n";}// Driver code.int main() { vector<int> values = {9, 1, 3}; int value = 6; int x = 9; Node* head = createList(values); Solution sol; head = sol.insertBeforeValueX(head, value, x); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), traversal may move across every node once before finding value X or reaching list end.
Space Complexity: O(1), only one dummy node, one new node, and one traversal pointer are used.
Interview follow-up Questions
The first occurrence gets targeted in the standard singly linked list version.
Be the first to add a comment.