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; } } |