Question

How to find middle element of linked list in java ?

Linked list: [10 40 5 50 20 30]

Answer 1

To find middle element in linked list. Count the all nodes and divided by 2. After that add 1 then get the middle of element in linked list.

See the following code:-

public class Node {

int data;

Node next = null;

public Node(int data) {

this.data = data;

}

}

/**

* Time Complexity O(n+n/2)

*/

public Node getMiddleNode() {

Node current = head;

int middle = getMiddleIndex();

while(current != null) {

if(middle == 1) {

return current;

}

middle--;

current = current.next;

}

return null;

}

private int getMiddleIndex() {

int totalNodes = getNodesCount();

int middle = totalNodes/2;

middle = middle+1;

return middle;

}

public int getNodesCount() {

return count;

}

In Test class type the following code:-

Node middleNode = linkedList.getMiddleNode();

System.out.println("\nMiddle Node of LinkedList:- "+ middleNode.data);

Output:-

Print LinkedList Data:- 

10 40 5 50 20 30 

Middle Node of LinkedList:- 50

Answer 2

To find the middle element of linked list in one traversal. See the following code:-

/**

* Time Complexity O(n)

*/

public Node getMiddleNodeUsingCountInOneTraversal() {

Node current = head;

Node mid = head;

int count = 0;

while(current != null) {

if(count%2 != 0) {

mid = mid.next;

}

count++;

current = current.next;

}

return mid;

}

Following code type into your test class:-

Node middleNode = linkedList.getMiddleNodeUsingCountInOneTraversal();

System.out.println("\nMiddle Node of LinkedList Using One References:- "+ middleNode.data);

Output:-

Print LinkedList Data:-

10 40 5 50 20 30

Middle Node of LinkedList Using One References:- 50

Answer 3

To find middle element of linked list by using two references one is slow and other one is fast reference. See the following code:-

/**

* Time Complexity O(n/2)

*/

public Node getMiddleNodeUsingTwoRereraces() {

Node slow = head;

Node fast = head;

while(fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

}

return slow;

}

Type the following code into your test class:-

Node middleNode = linkedList.getMiddleNodeUsingTwoRereraces();

System.out.println("\nMiddle Node of LinkedList Using Two References With n/2 traversal:- "+ middleNode.data);

Output:-

Print LinkedList Data:-

10 40 5 50 20 30

Middle Node of LinkedList Using Two References With n/2 traversal:- 50