Below is the simplest way to find Middle Element of LinkedList:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
package com.crunchify.tutorials; import java.util.LinkedList; import java.util.List; public class CrunchifyFindMiddleInLinkedList { /** * @author Crunchify.com */ public static void main(String[] args) { List<String> list = new LinkedList<String>(); for (int i = 0; i < 100; i++) { list.add(String.valueOf(i)); } System.out.println("Middle Element of Linked List is: " + FindMiddle1(list)); } private static String FindMiddle1(List<String> list) { int size = list.size(); int middle = (size / 2); return list.get(middle).toString(); } } |
Output:
|
1 |
Middle Element of Linked List is: 50 |
You should use – two pointer one increment at normal rate while other 2x rate. When the 2nd pointer hit the end of the list, the first pointer is at the middle of the list.
The downside with this is that java goes through half the linkedlist to get to the middle element. Take for example this code:
for (int i = 0; i < 100000; i++) {
list.add(String.valueOf(i));
System.out.println("Middle Element of Linked List is: " + FindMiddle1(list));
}
If one could actually get a pointer to the Node object used in the LinkedList one could easily have moved up or down one element until the middle is reached, but as far as I can see this is not possible.
What is the better way to make this code faster? Besides using an ArrayList?
Good start App Shah.. this site covers very important and deeper insightful questions in Java.
Thanks Puneet. Keep visiting and happy coding.