Insert Node Between Two Nodes

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given the head of a singly linked list, and two integers `a` and `b` representing the data of two consecutive nodes in the list, and an integer `x`, insert a new node with data `x` between the nodes with data `a` and `b`. It is guaranteed that nodes with data `a` and `b` exist and are adjacent. Return the head of the modified linked list.

Examples:

Input: head = [1, 2, 3, 4], a = 2, b = 3, x = 5

Output: [1, 2, 5, 3, 4]

Input: head = [10, 20, 30], a = 10, b = 20, x = 15

Output: [10, 15, 20, 30]

Input: head = [1, 2], a = 1, b = 2, x = 3

Output: [1, 3, 2]

Constraints

The number of nodes in the linked list is between 1 and 10^5.
Node values are integers in the range [-10^9, 10^9].
a and b are guaranteed to be present in the list and consecutive.
x is an integer.

Editorial

Intuition:

The key insight is that since a and b are guaranteed to be adjacent, we only need to locate the node with value a. Once found, inserting x between a and b is a matter of updating pointers: the new node's next points to b, and a's next points to the new node.

Approach:

Traverse the linked list to find the node whose data equals a and whose next node's data equals b.
Create a new node with data x.
Set the new node's next pointer to the node after a (the b node).
Update the a node's next pointer to the new node.
Return the head of the list (it remains unchanged because insertion occurs after a).

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode* insertNode(ListNode* head, int a, int b, int x) {
        ListNode* curr = head;
        while (curr && curr->next) {
            if (curr->val == a && curr->next->val == b) {
                ListNode* newNode = new ListNode(x);
                newNode->next = curr->next;
                curr->next = newNode;
                break;
            }
            curr = curr->next;
        }
        return head;
    }
};
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
class Solution {
    public ListNode insertNode(ListNode head, int a, int b, int x) {
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == a && curr.next.val == b) {
                ListNode newNode = new ListNode(x);
                newNode.next = curr.next;
                curr.next = newNode;
                break;
            }
            curr = curr.next;
        }
        return head;
    }
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def insert_node(head, a, b, x):
    curr = head
    while curr and curr.next:
        if curr.val == a and curr.next.val == b:
            new_node = ListNode(x)
            new_node.next = curr.next
            curr.next = new_node
            break
        curr = curr.next
    return head
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}
function insertNode(head, a, b, x) {
    let curr = head;
    while (curr && curr.next) {
        if (curr.val === a && curr.next.val === b) {
            const newNode = new ListNode(x);
            newNode.next = curr.next;
            curr.next = newNode;
            break;
        }
        curr = curr.next;
    }
    return head;
}

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case we traverse the entire list to find the (a, b) pair.

Space Complexity: O(1) additional space, as we only use a few pointers and the newly created node (which is part of the output and not counted as extra space).

Notes

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

Problem Categories