Java program to find middle element of linked list in one pass.

 Java program to find middle element of linked list in one pass. 

How do you find middle element of LinkedList in one pass is a programming question often asked to Java and non Java programmers in telephonic Interview. This question is similar to checking palindrome or calculating factorial, where Interviewer some time also ask to write code. In order to answer this question candidate must be familiar with LinkedList data structure i.e. In case of singly LinkedList, each node of Linked List contains data and pointer, which is address of next Linked List and last element of Singly Linked List points towards null. Since in order to find middle element of Linked List you need to find length of LinkedList, which is counting elements till end i.e. until you find the last element on Linked List. What makes this data structure Interview question interesting is that you need to find middle element of LinkedList in one pass and you don’t know length of LinkedList. This is where candidates logical ability puts into test,  whether he is familiar with space and time trade off or not etc. As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find length of Singly Linked List in Java. By using two pointers, incrementing one at each iteration and other at every second iteration. When first pointer will point at end of Linked List, second pointer will be pointing at middle node of Linked List.  In fact this two pointer approach can solve multiple similar problems e.g. How to find 3rd element from last in a Linked List in one Iteration or How to find nth element from last in a Linked List. In this Java programming tutorial we will see a Java program which finds middle element of Linked List in one Iteration.


package com.test;

/**
 * Java program to find middle element of linked list in one pass. In order to
 * find middle element of linked list we need to find length first but since we
 * can only traverse linked list one time, we will use two pointers one which we
 * will increment on each iteration while other which will be incremented every
 * second iteration. so when first pointer will point to the end of linked list,
 * second will be pointing to the middle element of linked list
 * 
 * @author captain
 */
public class LinkedListTest {

public static void main(String args[]) {
// creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
LinkedList.Node head = linkedList.head();
linkedList.add(new LinkedList.Node("1"));
linkedList.add(new LinkedList.Node("2"));
linkedList.add(new LinkedList.Node("3"));
linkedList.add(new LinkedList.Node("4"));

// finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;

while (current.next() != null) {
length++;
if (length % 2 == 0) {
middle = middle.next();
}
current = current.next();
}

if (length % 2 == 1) {
middle = middle.next();
}

System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);

}

}

class LinkedList {
private Node head;
private Node tail;

public LinkedList() {
this.head = new Node("head");
tail = head;
}

public Node head() {
return head;
}

public void add(Node node) {
tail.next = node;
tail = node;
}

public static class Node {
private Node next;
private String data;

public Node(String data) {
this.data = data;
}

public String data() {
return data;
}

public void setData(String data) {
this.data = data;
}

public Node next() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public String toString() {
return this.data;
}
}
}