Introduction
Given a singly linked list, find middle of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.
Approach
We use the tortoise and hare approach where we have a fast and a slow pointer. When the fast pointer reaches the end, the middle pointer reaches the middle position.
Code
/* Node of a linked list
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
*/
class Solution
{
int getMiddle(Node head)
{
// Your code here.
var slow = head;
var fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
}
}
References
Finding middle element in a linked list | Practice | GeeksforGeeks
Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.If there are even nodes, then there would be two middle nodes,
Find the middle of a given linked list in C and Java - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
