Find middle node in LinkedList
Algorithm to find middle node in LinkedList, To find middle node we will use two pointers P1 and P2, We will increment P2 after every two steps of P1.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Here we will get HEAD node Node n = createLinkedListData(11).head(); Node p1 = n.getNext(); Node p2 = p1; int index = 0; while (p1 != null) { p1 = p1.getNext(); index++; if (index % 2 == 0) { p2 = p2.getNext(); } } System.out.println("Middle Node is :" + p2.getData()); |
Entire Program
|
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 |
package com.omt.learn.crackingcodinginterview.linkedlist; import com.omt.learn.crackingcodinginterview.linkedlist.util.LinkedList; import com.omt.learn.crackingcodinginterview.linkedlist.util.LinkedList.Node; public class FindMiddleNodeLL { public static void main(String[] args) { Node n = createLinkedListData(11).head(); // while (n.getNext() != null) { // System.out.println(n.getNext().getData()); // n = n.getNext(); // } Node p1 = n.getNext(); Node p2 = p1; int index = 0; while (p1 != null) { p1 = p1.getNext(); index++; if (index % 2 == 0) { p2 = p2.getNext(); } } System.out.println("Middle Node is :" + p2.getData()); } public static LinkedList createLinkedListData(int dataCount) { LinkedList ll = new LinkedList(); for (int count = 1; count <= dataCount; count++) { ll.add(new LinkedList.Node(Integer.toString(count))); } return ll; } } |
