Saturday 28 May 2016

Find the middle node of linked list in one pass


Linked List is data structure which consist of nodes.Each node consist of data,previous node pointer and next node pointer.Previous node pointer points to previous node and next node pointer points to next node.Finding a middle node of linked list is one of important question asked in interview for experienced professionals.

Sample Program:-


 public class FindMiddleNodeInLinkedList {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           LinkedList linkedList = new LinkedList();  
           LinkedList.Node head = linkedList.head();  
           linkedList.add(new LinkedList.Node("10"));  
           linkedList.add(new LinkedList.Node("9"));  
           linkedList.add(new LinkedList.Node("8"));  
           linkedList.add(new LinkedList.Node("7"));  
           linkedList.add(new LinkedList.Node("6"));  
           LinkedList.Node current = head;  
           int length = 0;  
           LinkedList.Node middle = head;  
           while (current.next() != null) {  
                length++;  
                if (length % 2 == 0) {  
                     middle = middle.next();  
                }  
                current = current.next();  
           }  
           if (length % 2 == 1) {  
                middle = middle.next();  
           }  
           System.out.println(" Middle element of LinkedList is : " + middle);  
      }  
 }  
 class LinkedList {  
      private Node head;  
      private Node tail;  
      public LinkedList() {  
           this.head = new Node("head");  
           tail = head;  
      }  
      public Node head() {  
           return head;  
      }  
      public void add(Node node) {  
           tail.next = node;  
           tail = node;  
      }  
      public static class Node {  
           private Node next;  
           private String value;  
           public Node(String value) {  
                this.value = value;  
           }  
           public String value() {  
                return value;  
           }  
           public void setValue(String value) {  
                this.value = value;  
           }  
           public Node next() {  
                return next;  
           }  
           public void setNext(Node next) {  
                this.next = next;  
           }  
           public String toString() {  
                return this.value;  
           }  
      }  
 }  


Corner Cases:-
  • If only one node is present, then it will return the node.
  • If even number of nodes are present, then it will return middle element as the node which is exactly divisible by 2.


Enjoy Programming:)

No comments:

Post a Comment