This is how it works, there will be two pointers, one jumping once and another one jumping twice. When the double jumper ends/terminates, the single jump fellow’s data would be the center.
class Node { Object data; Node next; public Node( Object data, Node next ) { this.data = data; this.next = next; } } class LinkedList { Node head; public void addFirst( Object data ) { head = new Node( data, head ); } } public class LinkedListUtil { public static Node getMiddleNode( Node head ) { Node cursor = head; Node middle = head; while( cursor.next != null ) { // Move the cursor one step forward. // cursor = cursor.next; System.out.println("Cursor is "+cursor.data ); // Check if we've reached the end. // if( cursor.next != null ) { // Move the cursor one more step forward, // making it a total of two steps. // cursor = cursor.next; System.out.println("Cursor is again " +cursor.data ); // Move the middle cursor only one step forward. // middle = middle.next; System.out.println( "Middle is is "+middle.data ); } } return middle; } /** * Test Method */ public static void main( String[ ] args ) { // Initialize and populate the linked-list // LinkedList list = new LinkedList( ); for( int i = 1; i <= 15; i++ ) { list.addFirst( i ); } // Returns 3 as the middle node. // Node middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data ); list.addFirst( 6 ); // Returns 3 (again) as the middle node, since we have an even sized linked-list. // middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data); list.addFirst( 7 ); // Returns 4 as the middle node. // middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data ); } } class Node { Object data; Node next; public Node( Object data, Node next ) { this.data = data; this.next = next; } } class LinkedList { Node head; public void addFirst( Object data ) { head = new Node( data, head ); } } public class LinkedListUtil { public static Node getMiddleNode( Node head ) { Node cursor = head; Node middle = head; while( cursor.next != null ) { // Move the cursor one step forward. // cursor = cursor.next; System.out.println("Cursor is "+cursor.data ); // Check if we've reached the end. // if( cursor.next != null ) { // Move the cursor one more step forward, // making it a total of two steps. // cursor = cursor.next; System.out.println("Cursor is again " +cursor.data ); // Move the middle cursor only one step forward. // middle = middle.next; System.out.println( "Middle is is "+middle.data ); } } return middle; } /** * Test Method */ public static void main( String[ ] args ) { // Initialize and populate the linked-list // LinkedList list = new LinkedList( ); for( int i = 1; i <= 15; i++ ) { list.addFirst( i ); } // Returns 3 as the middle node. // Node middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data ); list.addFirst( 6 ); // Returns 3 (again) as the middle node, since we have an even sized linked-list. // middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data); list.addFirst( 7 ); // Returns 4 as the middle node. // middleNode = LinkedListUtil.getMiddleNode( list.head ); System.out.println( "Mid node is"+middleNode.data ); } }