Linked List: Insert node into the middle of the linked list

Problem Statement:

Given a LL and a number k, you need to insert k in the middle of the list.

The middle node is (n/2), and you need to insert in (n+1)/2

Example:

Input: 1 -> 2 -> 3 ->  k = 6

Output: 1 -> 2 -> 6 -> 3

Solution 1: Naive Approach

Find the length of the ll and insert the node after the middle node.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Efficient approach

We use slow_ptr and fast_ptr.

slow_ptr moves one step at a time.

fast_ptr moves 2 steps at a time.

Once fast_ptr reaches end, slow_ptr will point to the middle of the LL.

Then we insert the new node after the slow_ptr

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next;

    Node (int new_value)
    {
        data = new_value;
        next = NULL;
    }
}; 

void print_list(Node *head) 
{ 
  	Node* curr = head;

    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
} 

Node *solution_1 (Node *head, int x) 
{

    if (head == NULL) 
    {
        return new Node(x);
    }

    Node *newNode = new Node(x);
    Node *currNode = head;
    int length = 0;

    // get the legnth of the LL
    while (currNode != nullptr) 
    {
        length++;
        currNode = currNode->next;
    }

    
  	int mid;
    
    if (length % 2 == 0) 
    {
        mid = length / 2;
    }
    else 
    {
        mid = (length + 1) / 2;
    }

    currNode = head;

    // move to the position where the 
    // new node needs to be placed.
    while (mid > 1) 
    {
        currNode = currNode->next;
      	mid--;
    }

    newNode->next = currNode->next;
    currNode->next = newNode;

    return head;
}

Node *solution_2 (Node *head, int x) 
{
  
    
    if (head == NULL) 
    {
        return new Node(x);
    }
    else 
    {
      
        Node *newNode = new Node(x);

        Node *slow_ptr = head;
        Node *fast_ptr = head->next;

        while (fast_ptr && fast_ptr->next) 
        {
            slow_ptr = slow_ptr->next;
            fast_ptr = fast_ptr->next->next;
        }

        newNode->next = slow_ptr->next;
        slow_ptr->next = newNode;

        return head;
    }
}


int main() 
{ 
    
    Node *head = new Node(1); 

    // Created linked list will be 1 -> 2 -> 3 -> 4 -> 5
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    int k = 9;
    print_list(head);

    head = solution_1(head, k);
    print_list(head);

    k = 10;
    head = solution_2(head, k);
    print_list(head);

    return 0; 
} 

Output

1 2 3 4 5 
1 2 3 9 4 5 
1 2 3 10 9 4 5