Teaching Kids Programming – Fast and Slow Pointer to Obtain the Middle of the Linked List

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a head of the linked list, how do we efficiently get the middle of the linked list? Sure we can follow the linked list once and count the number of the nodes. Once we reach the end, we know the middle of linked list immediately by halvening the total number of nodes. This time complexity is O(N) and we need to traverse the linked list 1.5 times.

We can do better in O(N) time and only traverse the linked list exactly once. We can use two pointers: fast and slow. The fast pointer traverse two steps at a time, and the slow pointer traverses one step at a time. When the fast pointer reaches the end, the slow pointer points to the middle node.

class Node:
	def __init__(self, val, nextNode = None):
		self.val = val
		self.nextNode = nextNode

	def addNode(self, val):
		newNode = Node(val)
		self.nextNode = newNode
		return newNode

head = Node(1)
p = head
for i in range(2, 10):
	p = p.addNode(i)

# get the middle of the linked list
def mid(head):
	fast, slow = head, head
	while fast is not None and fast.nextNode is not None:
		fast = fast.nextNode.nextNode
		slow = slow.nextNode
	return slow

m = mid(head)
print(m.val)  # middle node is 5

See other implementations of getting the middle of the linked list:

• Fast and Slow Pointer to Get the Middle of the Linked List
• Teaching Kids Programming – Fast and Slow Pointer to Obtain the Middle of the Linked List
• How to Compute the Middle of the Linked List using Fast and Slow Pointer?
• GoLang: Compute the Middle of a Linked List

–EOF (The Ultimate Computing & Technology Blog)