Finding Middle element of linked list in one pass

Discovering Middle component of connected rundown in one pass

In the event that you need to hone information structure and calculation programs, you can experience information structure and calculation enquiries questions.

This is one of the famous enquiry question.

In this post, we will talk about how to discover centre component in linked list in most effective way.

Supposition: 

I am not utilizing java LinkedList API here. In the event that you utilize that API, you can straightforwardly discover size of linkedlist utilizing size() capacity and after that find length/2.

One of the algo for this would be:

Cross the rundown and discover the length of rundown

In the wake of discovering length, again cross the rundown and find n/2 component from head of linkedlist.

Time complexity=time for discovering length of rundown + time for finding center element=o(n)+o(n) =o(n)

Space complexity= o(1).

Productive approach: 

Above approach will take two traversal yet we can discover center component in one traversal additionally utilizing following algo:

Utilize two pointer fastptr and slowptr and introduce both to head of linkedlist

Move fastptr by two hubs and slowptr by one hub in every emphasis.

At the point when fastptr achieves end of hubs, the slowptr pointer will point center component.


public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// This function will find middle element in linkedlist
public Node findMiddleNode(Node head)
{
Node slowPointer, fastPointer;
slowPointer = fastPointer = head;

while(fastPointer !=null) {
fastPointer = fastPointer.next;
if(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
}

return slowPointer;

}

public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node head=new Node(5);
list.addToTheLast(head);
list.addToTheLast(new Node(6));
list.addToTheLast(new Node(7));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));

list.printList();
// finding middle element
Node middle= list.findMiddleNode(head);
System.out.println("Middle node will be: "+ middle.value);

}

}

Run above program, you will get following output:
5 6 7 1 2 
Middle node is: 7