Given a linked list of n nodes. The problem is to insert a new node with data x in the middle of the list. If n is an even number, insert a new node after the (n/2)th node, otherwise insert a new node after the (n+1)/2th node.

Examples: 

Input : list: 1->2->4->5
        x = 3
Output : 1->2->3->4->5

Input : list: 5->10->4->32->16
        x = 41
Output : 5->10->4->41->32->16

Method 1(Using length of the linked list): 

Use one traversal to find the number of nodes or length of the link. Let it be Lun. Calculate c = (len/2) if len is even, otherwise c = (len+1)/2, if len is odd. Traverse the first c nodes again and insert a new node after the c-th node.

JAVA:

// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;

class LinkedList
{
	static Node head; // head of list

	/* Node Class */
	static class Node {
		int data;
		Node next;
		
		// Constructor to create a new node
		Node(int d) {
			data = d;
			next = null;
		}
	}

	// function to insert node at the
	// middle of the linked list
	static void insertAtMid(int x)
	{
		// if list is empty
		if (head == null)
			head = new Node(x);
		else {
			// get a new node
			Node newNode = new Node(x);

			Node ptr = head;
			int len = 0;

			// calculate length of the linked list
			//, i.e, the number of nodes
			while (ptr != null) {
				len++;
				ptr = ptr.next;
			}

			// 'count' the number of nodes after which
			// the new node is to be inserted
			int count = ((len % 2) == 0) ? (len / 2) :
										(len + 1) / 2;
			ptr = head;

			// 'ptr' points to the node after which
			// the new node is to be inserted
			while (count-- > 1)
				ptr = ptr.next;

			// insert the 'newNode' and adjust
			// the required links
			newNode.next = ptr.next;
			ptr.next = newNode;
		}
	}

	// function to display the linked list
	static void display()
	{
		Node temp = head;
		while (temp != null)
		{
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
	}

	// Driver program to test above
	public static void main (String[] args)
	{
		// Creating the list 1.2.4.5
		head = null;
		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(4);
		head.next.next.next = new Node(5);
		
		System.out.println("Linked list before "+
						"insertion: ");
		display();

		int x = 3;
		insertAtMid(x);

		System.out.println("\nLinked list after"+
						" insertion: ");
		display();
	}
}

// This article is contributed by Chhavi

Output: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Time Complexity: O(n)

Method 2(Using two pointers): Based on the Turtle and Rabbit algorithm that uses two pointers, one is known to be slow and the other is known to be fast. This algorithm helps to find the middle node of the linked list. This is explained in the procedure for front and black separation of this post. You can now insert a new node after the middle node you got from the above process. This approach only requires crawling the list.

// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;

class LinkedList
{
	static Node head; // head of list

	/* Node Class */
	static class Node {
		int data;
		Node next;
		
		// Constructor to create a new node
		Node(int d) {
			data = d;
			next = null;
		}
	}

	// function to insert node at the
	// middle of the linked list
	static void insertAtMid(int x)
	{
		// if list is empty
		if (head == null)
		head = new Node(x);

		else {
			// get a new node
			Node newNode = new Node(x);

			// assign values to the slow
			// and fast pointers
			Node slow = head;
			Node fast = head.next;

			while (fast != null && fast.next
								!= null)
			{
				// move slow pointer to next node
				slow = slow.next;

				// move fast pointer two nodes
				// at a time
				fast = fast.next.next;
			}

			// insert the 'newNode' and adjust
			// the required links
			newNode.next = slow.next;
			slow.next = newNode;
		}
	}

	// function to display the linked list
	static void display()
	{
		Node temp = head;
		while (temp != null)
		{
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
	}

	// Driver program to test above
	public static void main (String[] args)
	{
		// Creating the list 1.2.4.5
		head = null;
		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(4);
		head.next.next.next = new Node(5);
		
		System.out.println("Linked list before"+
						" insertion: ");
		display();

		int x = 3;
		insertAtMid(x);

		System.out.println("\nLinked list after"+
						" insertion: ");
		display();
	}
}

// This article is contributed by Chhavi

Output: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Time Complexity: O(n)