Middle of the Linked List

We will be given a linked list, need to return the middle node of the linked list

Example 1: Linked List with Odd number of nodes

Output = 3

Example 2: Linked List with Even number of nodes

Output = 4

For Even List [3, 4] both can be middle but according to the problem description we need return the Second Middle node. Read the problem description for more details.

Intuition

Let's take the Even List (second example) to elaborate the problem. We all know that NULLis the next node of the Last node of Linked List. To solve this problem we will use a special version of Two Pointer algorithm known as Slow Fast Pointer which will look like this

Slow will move one step and Fast will jump two steps at a time. When the Fast pointer reaches at the End of the Linked List (for Linked List Even number of nodes, Fast will reach Node before NULL but not the NULL), the Slow will be pointing at the Middle Node. But before dive into the problem, let's build a general concept.

General Concept

Let's assume, you (S) and your friend (F) are standing at the First Floor, going climb the stairs (Nodes in the Linked List) to reach at the Second Floor. But you knee is hurting so you can only climb 1 staircase at a time while your friend can jump 2 stairs at a time. So by the time your friend reach at the Second Floor and you will be Half Way on the stairs. Let's visualize

Mathematical Proof

As we can see Your friend (F) reached at the 2nd Floor while you are on the Middle of the stairs.
Because F has 2x speed of S. Let's prove it mathematically. So the distance D = 5 (number of stairs)

Let, D = 5
=> F = 2(S)
=> S = F/2

When F reached at D then F = D, Hence our equation will look like

=> S = D/2
=> S = 5/2
=> S = 2.5  # let's round it up
=> S ~= 3 [proved]

Hence S will be at the middle when F reached at the destination. To wrap it up, put this understanding with our Given Linked List.

Pointer Placement

# Definition for singly-linked list.
# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next

class Solution:
	def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
		slow = head
		fast = head

Now Slow and Fast will move forward until Fast reaches at the End of the List. Let's visualize first, then we will see the implementation

Find the Middle Node

As the First is pointing at the NULL means our Slow pointer has reached at the Middle Node of the Linked List (For Linked List with even number of nodes, we can consider the second middle).
Let's write the whole code

Complete Code Snippet

class Solution:
	def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			# this is why fast.next check is added in the while loop
			fast = fast.next.next
		return slow

So that's it. This problem is pretty basic which we will see working as a Template for other Medium and Hard category problems.

Connect with me on