Insert node in the middle of a Linked List

by

When we have a singly linked list, the task is to update the linked list by adding a new node in the middle of the linked list. If the size of the linked list, size is even, then the new node is to be added at (size/2) position or else if the length is odd then it should be added at (size+1)/2 position.

This can be attained by finding out the length of the linked list and then inserting the node at a desired position. But in this tutorial, we would look at a much optimized approach with a slow pointer and a fast pointer. Let’s understand the intuition behind the algorithm.

Intuition behind Algorithm

Let’s say for a linked list having 4 nodes. We start by two pointers pointing to the first node (head). Then we start moving the first pointer by 1 position while we update the second pointer with two positions, so when the second pointer will be at the last node, the first pointer will be at the middle position. We would update this position with the new node.

Algorithm

  1. Declare two pointers with initial value as that of head position.
  2. Move first pointer (slowPointer) with one positions and second pointer (fastPointer) with two positions until fastPointer reaches the last node.
  3. Insert a new node at the place of the slowPointer.

Java Code for the algorithm

public class LinkedList {

	// Creating a sub class Node. This will act as each node of a linkedlist
	class Node {
		int value;
		Node next;

		Node(int value){
			this.value = value;
			this.next = null;
		}
	}

	Node head;

	public void addNode(int value) {
		Node newNodeToAdd = new Node(value);
		if(head == null) {
			this.head = newNodeToAdd;
		} else {
			Node tail = this.head;
			while (tail.next != null) {
				tail = tail.next;
			}
			tail.next = newNodeToAdd;
		}
		
	}

         public void addNodeInMiddle(int value) {
		Node newNodeToAdd = new Node(value);
		
		Node slowPointer = this.head;
		Node fastPointer = this.head;
		
		while(fastPointer != null && fastPointer.next != null) {
			slowPointer = slowPointer.next;
			fastPointer = fastPointer.next.next;
		}
		
		newNodeToAdd.next = slowPointer.next;
		slowPointer.next = newNodeToAdd;
	}

         public static void main(String[] args) {
		LinkedList linkedList = new LinkedList();
		
		linkedList.addNode(11);
		linkedList.addNode(12);
		linkedList.addNode(13);
		linkedList.addNode(14);
		linkedList.addNode(15);
		
		linkedList.showList();
		System.out.println("--------------------");
		
		System.out.println("After Adding node in the Middle");
		linkedList.addNodeInMiddle(1010);
		linkedList.showList();
          }
  }
Output:

11
12
13
14
15
--------------------
After Adding node in the Middle
11
12
13
1010
14
15

The above code implements the discussed algorithm in the method addNodeInMiddle(int value). The general addNode(int value) method to add a node in the end is discussed in our previous tutorial. You can check that out here.

Leave a Comment