How to find middle element of Linked List in one pass?
How to find middle element of Linked List in one pass?
This is frequently asked question for Java developers, How to find middle element of LinkedList in one pass if size is not given. In order to answer this question we need to understand how Linked List works. In case of singly linked list, each node contains data and next pointer. data holds the value and next pointer points to the next node, which holds address of the next node. And last element points to the null.
To find middle element of the linked list, first we need to find length of the linked list, for which we have to iterate through the list till end to find the length. If you think carefully this can be solved easily by 2 pointers, where first pointer points increments by 1 and second pointer increments by 2. So, when second pointer reaches the end of the linked list, first pointer will at the middle of the linked list.
Java program to find middle element of the Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public class LinkedLists { Node head; static class Node{ int data; Node next; Node(int data){ this.data = data; this.next = null; } } public void push(int data){ Node newNode = new Node(data); newNode.next = head; head = newNode; } public void print(){ Node n = head; while(n != null){ System.out.print("-> "+n.data); n = n.next; } System.out.println(""); } /** * find middle without using size * use fast and slow pointer to find middle element * */ public void printMiddle(){ Node fast = head; Node slow = head; while(fast!=null && fast.next !=null){ slow = slow.next; fast = fast.next.next; } System.out.println("Middle->"+slow.data); } public static void main(String[] args) { LinkedLists llist = new LinkedLists(); //Initialize linked list value for (int i=5; i>0; --i){ llist.push(i); llist.print(); } llist.printMiddle(); } } |
Output:
|
1 2 3 4 5 6 |
-> 5 -> 4-> 5 -> 3-> 4-> 5 -> 2-> 3-> 4-> 5 -> 1-> 2-> 3-> 4-> 5 Middle Element ->3 |
Further Reading
Thanks you have explained it very clearly. Can you also write a post on how to find nth element ?