# How to find middle element of linked list in java ?

50 views
How to find middle element of linked list in java ?

Linked list: [10 40 5 50 20 30]

by (2.8k points)

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() {

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:-

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

Output:-

10 40 5 50 20 30

by (2.8k points)
To find the middle element of linked list in one traversal. See the following code:-

/**

* Time Complexity O(n)

*/

public Node getMiddleNodeUsingCountInOneTraversal() {

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:-

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

Output:-

10 40 5 50 20 30

Middle Node of LinkedList Using One References:- 50
by (2.8k points)
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() {

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

slow = slow.next;

fast = fast.next.next;

}

return slow;

}

Type the following code into your test class:-