How will you find the middle of the Linked List?

To find the middle of a linked list we can use many approaches. let's discuss our first approach having O(n) time complexity with 2 passes.

We will be calculating the length n of the linked list in the first iteration and in second iteration we will be traversing to n/2 length to get the middle of the linked list.

Can we do it in just 1 iteration?

Yes, we can use two pointers, 1 slow pointer and 1 fast pointer. we will be moving fast pointer two steps per iteration while slow pointer will move only one step per iteration. So when the fast pointer will reach the end of the linked list then the slow pointer will be at the middle of the linked list.

Java implementation of the above solution is as below:

package askgif.linkedlist;

import java.util.Stack;

class ListNode{
 public int data;
 public ListNode next;
 ListNode(int data){
 	this.data = data;
 }
};

public class LinkedListNode {

	public static void main(String[] args) {
		
 ListNode node1 = new ListNode(1);
 ListNode node2 = new ListNode(2);
 ListNode node3 = new ListNode(3);
 ListNode node4 = new ListNode(4);
 ListNode node5 = new ListNode(5);
 ListNode node6 = new ListNode(6);
 ListNode node7 = new ListNode(7);
 ListNode node8 = new ListNode(8);
 ListNode node9 = new ListNode(9);
 ListNode node10 = new ListNode(10);
 ListNode node11 = new ListNode(11);
 
 node1.next = node2;
 node2.next = node3;
 node3.next = node4;
 node4.next = node5;
 node5.next = node6;
 node6.next = node7;
 node7.next = node8;
 node8.next = node9;
 node9.next = node10;
 node10.next = node11;
 node11.next = null;
 
		System.out.println(GetMiddleElement( node1));
		

	}

	private static int GetMiddleElement(ListNode node1) {
		
		ListNode slowPtr = node1;
		ListNode fastPtr = node1;
		
		while(fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}
		
		return slowPtr.data;
	}

}

output:

6

The time complexity of the above solution is O(n) and the space complexity is also O(n).