LINK01P11 - Editorial

editorial
, , ,
1

Problem Link: Linked List - Insertion at k-th position

Problem Solution:

To insert a node in between the k and k+1 node, we will have to change the next pointer of both the k-th node and new Node.

  1. Set next of new Node to next of current
  2. Set next of current to new Node

Approach:

The code snippet defines the function insertAfterK which inserts a new node with a given value after the k-th node in a linked list.

  1. Creating a New Node: A new node is created using newNode = new Node(value) which stores the given value.

  2. Handling an Empty List: If the linked list is empty (head == NULL), the new node becomes the head of the list, and the function returns.

  3. Traversing to the k-th Node: The function traverses the list until it reaches the k-th node using a loop.

  4. Inserting the New Node:

    • Setting the Next Pointer: The line newNode -> next = current -> next; connects the newly created node (newNode) to the node that comes after the k-th node. This ensures that the new node is inserted correctly between the k-th node and its next node.

    • Updating the k-th Node: The line current -> next = newNode; makes the k-th node point to the newly created node (newNode), thereby completing the insertion.

This process ensures that the new node is inserted right after the k-th node, maintaining the correct structure of the linked list.

Time Complexity:

  • O(k) since the function traverses the list up to the k-th node.

Space Complexity:

  • O(1) as no extra space is used apart from the new node.