Find middle node in linkedlist

Greeks reference.

/** 
 * Two approaches can be used here :
 * 1. Take fast and slow pointer. Slow pointer move 1 step ahead and fast pointer moves
 * 2 steps ahead. When fast pointer reached last then slow reaches to middle 
 * 2. Traverse to floor(size of linkedlist)/2 nodes or Traverse to ceil(size of 
 * linkedlist)/2 nodes based on demand.
 */
class FindMiddleOfLinkedList {
    static Node head;
    
    static int findMiddle() {
        Node slow, fast;
        slow = fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.data;
    }
    
    static void create(int[] data) {
        head = new Node();
        head.data = data[0];
        Node last = head;
        for(int i = 1; i < data.length; i++) {
            Node temp = new Node();
            temp.data = data[i];
            last.next = temp;
            last = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] data = new int[] {1, 2, 3, 4, 5};
        create(data);
        System.out.println("middle element : " + findMiddle());
        data = new int[] {1, 2, 3, 4};
        create(data);
        System.out.println("middle element : " + findMiddle());
    }

	private static class Node {
	    Node prev;
	    int data;
	    Node next;
	}
}

Output
middle element : 3
middle element : 2

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance