Find middle element in circular linked list
In the problem of finding the middle element in a circular linked list, we are dealing with a data structure called a circular linked list. A circular linked list is a variation of a traditional linked list where the last node points back to the first node instead of having a NULL reference. The challenge is to find the middle element of this circular linked list, which is not a trivial task due to the circular nature of the structure.
Problem Statement
Given a circular linked list, we need to find the middle element in the list. If the number of nodes in the list is odd, the middle element is the one exactly in the middle. If the number of nodes is even, there are two middle elements, and we can choose either of them as the middle element.
Example
Consider a circular linked list with the following elements: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7. The middle element in this case is 4.
Idea to Solve the Problem
To find the middle element in a circular linked list, we can use the "tortoise and hare" approach. In this approach, two pointers traverse the linked list at different speeds. The slower pointer (tortoise) moves one step at a time, while the faster pointer (hare) moves two steps at a time. When the faster pointer reaches the end of the list, the slower pointer will be at the middle element.
Pseudocode
Here's the pseudocode to find the middle element in a circular linked list using the "tortoise and hare" approach:
function findMiddle(circularLinkedList):
if circularLinkedList.head is NULL:
print "Empty Linked List"
else:
tortoise = hare = circularLinkedList.head
while hare is not NULL and hare.next is not circularLinkedList.head:
hare = hare.next.next
tortoise = tortoise.next
print "Middle Node is:", tortoise.data
Algorithm Explanation
- Start with both the
tortoise
andhare
pointers pointing to the head of the circular linked list. - Loop while
hare
is not NULL andhare.next
is not pointing back to the head. This condition ensures thathare
traverses the list twice as fast astortoise
. - In each iteration, move
hare
two steps ahead andtortoise
one step ahead. - When the loop exits,
tortoise
will be at the middle element of the list.
Program List
-
1) Find middle element of circular linked list in c++
2) Find middle element of circular linked list in c
3) Find middle element of circular linked list in java
4) Find middle element of circular linked list in golang
5) Find middle element of circular linked list in c#
6) Find middle element of circular linked list in vb.net
7) Find middle element of circular linked list in php
8) Find middle element of circular linked list in node js
9) Find middle element of circular linked list in typescript
10) Find middle element of circular linked list in python
11) Find middle element of circular linked list in ruby
12) Find middle element of circular linked list in scala
13) Find middle element of circular linked list in swift
14) Find middle element of circular linked list in kotlin
Resultant Output Explanation
For the provided example with the circular linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, the program will output:
Middle Node is : 4
This is the correct output since the middle element of the list is indeed 4.
Time Complexity
The time complexity of finding the middle element using the "tortoise and hare" approach is O(n), where n is the
number of nodes in the circular linked list. This is because the faster pointer (hare
) traverses the
list twice as fast as the slower pointer (tortoise
), leading to a linear traversal of the list. The
space complexity is O(1) as we are using only two pointers regardless of the size of the list.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment