Question: Middle of the Linked List
For odd length Linkedlist, we'll be having only one middle element, while for the even length, we'll have 2 middle elements.
In the question, they asked to return the 2nd node if there are 2 middle elements.
Step-1: initialize 2 pointers and name them as slow and fast
Step-2: Move the slow pointer one step at a time, and move the fast pointer 2 steps at a time.
In the beginning, both slow and fast are at the head of the linked list. Let's look into an example with odd length LinkedList
As we said in step-2 slow moves 1 step, while fast moves 2 steps simultaneously.
So when slow moves to 10 from -2, fast moves to 0 from -2
From -2 slow moves to 0 and from 0 fast moves to 4.
As we can see in the image below the slow pointer has reached the middle element.
An example of Even length Linkedlist:
In the above image you can see that the slow pointer reached mid1, when fast.next.next==None, we know that mid2 can be accessed as mid1.next
Step-3:
When the no. of elements in the linked list are odd we get to the middle element
when->fast.next is None,
while the no. of elements in linkedlist are even, we get to mid1 if-> fast.next.next is None.
Give a try to write the code with the above-explained logic before heading to see the code snippet.
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow=head
fast=head
while(fast.next!=None and fast.next.next!=None):
slow=slow.next
fast=fast.next.next
if fast.next==None:
return(slow)
else:
return(slow.next)
Thank you for reading till the end, hope you understood the logic 😊 .