Insert in Middle of Linked List

Problem

Given a linked list of size N and a key. The task is to insert the key in the middle of the linked list.

Examples:

Example 1:

Input:
LinkedList = 1->2->4
key = 3
Output: 1 2 3 4
Explanation: The new element is inserted after the current middle element in the linked list.

Example 2:

Input:
LinkedList = 10->20->40->50
key = 30
Output: 10 20 30 40 50
Explanation: The new element is inserted after the current middle element in the linked list and Hence, the output is 10 20 30 40 50.

Your task:

The task is to complete the function insertInMiddle() which takes head reference and element to be inserted as the arguments. The printing is done automatically by the driver code.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^4$

Solution

Python

def insertInMid(head, node):
    if head is None:
        return node
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    node.next = slow.next
    slow.next = node
    return head

Java

public Node insertInMid(Node head, int data){
    Node newNode = new Node(data);
    if (head == null) {
        return newNode;
    }
    Node slow = head;
    Node fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    newNode.next = slow.next;
    slow.next = newNode;
    return head;
}

C++

Node* insertInMiddle(Node* head, int x) {
	Node* newNode = new Node(x);
    if (head == nullptr) {
        return newNode;
    }
    Node* slow = head;
    Node* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    newNode->next = slow->next;
    slow->next = newNode;
    return head;
}

C

struct Node* insertInMiddle(struct Node* head, int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;
    if (head == NULL) {
        return newNode;
    }
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    newNode->next = slow->next;
    slow->next = newNode;
    return head;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$