Skip to content

03. Fast and Slow Pointers

Theory

Description

The Fast and Slow Pointer technique, also called the Tortoise and Hare algorithm, is a powerful method for efficiently solving problems in linked lists and cyclic structures.

How It Works

  • The slow pointer moves one step at a time.
  • The fast pointer moves two steps at a time.

The difference in speeds allows the fast pointer to catch up with the slow pointer if there’s a cycle or to identify the middle of a structure.

Key Insights

  • Cycle Detection: If a cycle exists, the fast pointer will meet the slow pointer inside the cycle.
  • Middle Element: The slow pointer will be at the middle when the fast pointer reaches the end.
  • Pattern Matching: Helps detect patterns like palindromes by dividing the structure into two parts.

Benefits

  • Time Efficient: Solves problems in O(n) time with a single traversal.
  • Space Efficient: Requires O(1) space, avoiding extra data structures.
  • Simple & Elegant: Reduces complex problems to simple solutions.

Problems

1. Linked List Cycle (Leetcode:141)

Problem Statement

Code and Explaination 

1
2
3
4
5
6
7
8
9
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
    slow, fast = head,head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
Explaination:
This is first approach

1
Explaination:
This is second approach

2. Linked List Cycle II (Leetcode:142)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

3. Happy Number (Leetcode:202)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

4. Middle of the Linked List (Leetcode:876)

Problem Statement

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow
Explaination:
This is first approach

1
Explaination:
This is second approach

5. Palindrome Linked List (Leetcode:234)

Problem Statement

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next 

    prev, curr = None, slow 

    while curr:
        nxt = curr.next 
        curr.next = prev 
        prev = curr
        curr = nxt 

    first_half, reversed_half = head, prev 

    while first_half and reversed_half:
        if first_half.val != reversed_half.val:
            return False 

        first_half = first_half.next 
        reversed_half = reversed_half.next 

    return True
Explaination:
This is first approach

1
Explaination:
This is second approach

6. Reorder List (Leetcode:143)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

7. Circular Array Loop (Leetcode:457)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

8. Remove Nth Node From End of List (Leetcode:19)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

9. Rotate List (Leetcode:61)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

10. Find the Duplicate Number (Leetcode:287)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

11. Moving Stones Until Consecutive II (Leetcode:1040)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

12. Remove Duplicates from Sorted List II (Leetcode:82)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

13. Friends Of Appropriate Ages (Leetcode:825)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

14. Partition Labels (Leetcode:763)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

15. Longest Mountain in Array (Leetcode:845)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

16. Count Pairs Of Nodes (Leetcode:1782)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach