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
Post a Comment