Find middle node of a LinkedList

Finding the middle node of a linked list by traversing the list twice is trivial. But what makes this problem interesting is; If you have to do this in a single pass/traversal. 

Here, I will be using Java to solve this problem. Java provides a built-in API LinkedList, so using inbuilt iterator and size method of this API, the middle element can be easily found. But that would defy the whole intention behind this problem. Better do it more crude way! 

In Linked List post, I have created a custom single linked list. I am reusing the same class here, and have added a new method/s to find the middle node.

Find Middle Node

Approach to find the middle node is: keep two references, one pointing to middle and other pointing to end of the list. Keep on traversing the list and make sure that middle reference always points to the middle node at any point of traversal. Done!!!

package algo;  
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar  
  *   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
      /**  
       * Node class  
       */  
      private static class Node<E> {  
           E data;  
           Node<E> next;  
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
           public E getData() {  
                return data;  
           }  
           public Node<E> getNext() {  
                return next;  
           }  
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
      public void add(E d) {
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.getNext() != null) {  
                     tmp = tmp.getNext();  
                }  
                tmp.setNext(new Node<E>(d, null));   // add at the end of list  
           }  
      }  
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
      /**  
       * Finds middle object/node of linked list  
       * Approach : increment middle node alternate time 

       * (i.e. when count is odd)  
       */  
      public Node<E> findMiddleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           int count = 0;  
           while (end != null) {  
                end = end.getNext();  
                // move middle pointer alternate times  
                if (count % 2 == 1) {  
                     middle = middle.getNext();  
                }  
                count++;  
           }  
           return (Node<E>) middle;  
      }  
      /**  
       * Find middle node - Alternate approach 
       *   
       */  
      public Node<E> middleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           while (end != null) {  
                end = end.getNext();  
                if (end != null) {  
                     end = end.getNext();  
                     middle = middle.getNext();  
                }  
           }  
           return (Node<E>) middle;  
      }  
      public static void main(String[] args) {  
           SingleLinkedList<Integer> sll = new SingleLinkedList<>();  
           sll.add(1);  
           sll.add(2);  
           sll.add(3);  
           sll.add(4);  
           sll.add(5);  
           sll.add(6);  
           sll.add(7);  
           sll.print();  
           Node<Integer> middle = sll.middleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
           middle = sll.findMiddleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
      }  
 } 

Output:

 values in link-list are :1--> 2--> 3--> 4--> 5--> 6--> 7--> null
Middle value --:4
Middle value --:4

Note that there are two methods to find the middle node; both are more or less same, though.

Complexity:
End reference traverses the list fully once (i.e. O(n) ) and middle reference traverses only till the middle of the list (i.e. n/2 nodes / O(n)). Summing up those two still makes its complexity as O(n).

You can use this approach to solve similar problems:

• Find the nth node from the last.
• Remove the middle node of the list. 
• Pairwise swapping of nodes (1->2->3->4 becomes 2->1->4->3)
• Split a linked list in 2 ( or 3) equal  or close to equal linked list
• Delete the repeated elements from a linked list.
• Append last n nodes of the list to the beginning.