Theory

The Fast & Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/LinkedList) at different speeds. This approach is quite useful when dealing with cyclic LinkedLists or arrays.

By moving at different speeds (say, in a cyclic LinkedList), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

One of the famous problems solved using this technique was Finding a cycle in a LinkedList.

Question

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

Example 1:
    1 -> 2 -> 3 -> 4 -> 5 -> 6
              |_ _ _ _ _ _ _ |
    there's a cycle from 6 -> 3

Example 2:
    2 -> 4 -> 6 -> 8 -> 10 -> null
    there's no cycle

Implementation: LinkedListCycle

The logic is to have two pointers: one slow and one fast. Two situations can arise: 1. If there's no cycle, the fast pointer reaches the end of the list. 2. If there's a cycle, the fast pointer catches up with the slow pointer.

Time complexity

O(n), since the fast pointer will travel n nodes.

Space complexity

O(1), we are not storing anything.

Given the head of a LinkedList with a cycle, find the length of the cycle.

    1 -> 2 -> 3 -> 4 -> 5 -> 6
              |_ _ _ _ _ _ _ |

    Length of cycle is 4 (3 -> 6)

Implementation: LengthOfCycle

We find a meeting point of the slow and fast pointers using the method above. Once we do, we start a third pointer and keep iterating till the slow and third pointers meet again.

The logic is:

Regardless of where the third and slow pointer meets, its will always have travelled the full loop, as shown in the diagram above.

Time complexity

O(n)

Space complexity

O(1)

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

    1 -> 2 -> 3 -> 4 -> 5 -> 6
              |_ _ _ _ _ _ _ |

    start is 3.

Implementation: LinkedListStart

The algorithm is: we find the length of the cycle. We substract that from the total length and the difference must be the index where the cycle starts. However, there's an issue with this approach. To find the total length, we will have to use O(n) space, which we don't want to.

Instead, we: 1. Find the cycle length. 2. Take two pointers, say: ptr1 and ptr2. 3. Move ptr2 by the length of the cycle. 4. Keep moving both till they meet. 5. The meeting point is the start of the cycle.

Time complexity

O(n)

Space complexity

O(1)

Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’. All other (not-happy) numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’.

Example 1:

Input: 23   
Output: true (23 is a happy number)  
Explanations: Here are the steps to find out that 23 is a happy number:

    2^2 + 3^2 = 13
    1^2 + 3^2 = 10
    1^2 + o^2 = 1

Example 2:

Input: 12   
Output: false (12 is not a happy number)  
Explanations: Here are the steps to find out that 12 is not a happy number:

    12+221^2 + 2 ^21​2​​+2​2​​ = 1 + 4 = 5
    525^25​2​​ = 25
    22+522^2 + 5^22​2​​+5​2​​ = 4 + 25 = 29
    22+922^2 + 9^22​2​​+9​2​​ = 4 + 81 = 85
    82+528^2 + 5^28​2​​+5​2​​ = 64 + 25 = 89
    82+928^2 + 9^28​2​​+9​2​​ = 64 + 81 = 145
    12+42+521^2 + 4^2 + 5^21​2​​+4​2​​+5​2​​ = 1 + 16 + 25 = 42
    42+224^2 + 2^24​2​​+2​2​​ = 16 + 4 = 20
    22+022^2 + 0^22​2​​+0​2​​ = 4 + 0 = 4
    424^24​2​​ = 16
    12+621^2 + 6^21​2​​+6​2​​ = 1 + 36 = 37
    32+723^2 + 7^23​2​​+7​2​​ = 9 + 49 = 58
    52+825^2 + 8^25​2​​+8​2​​ = 25 + 64 = 89

Step ‘13’ leads us back to step ‘5’ as the number becomes equal to ‘89’, this means that we can never reach ‘1’, therefore, ‘12’ is not a happy number.

With squaring and adding, it always goes into a cycle. However, if its a happy number, the cycle loops with 1, else it returns to the starting number and loops again.

Our logic is to detect the cycle and then check what number it loops with. If its a happy number, it will loop with 1, else it will loop with some other number.

Time complexity

O(logn)

Space complexity

O(1)

Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList. If the total number of nodes in the LinkedList is even, return the second middle node.

Example 1:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3

Example 2:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: 4

Example 3:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Output: 4

Implementation: LinkedListMiddle

For odd case,

1 -> 2 -> 3 -> 4 -> 5 -> null

there are 5 nodes in the list. 5/2 = 2. With 0-based index, that's node 3, which is the correct answer.

For even case,

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

there are 6 nodes in the list. 6/2 = 3. With 0-based index, that's node 4, which is the correct answer.

So, we need to calculate the total length of the list. Then divide by 2, which will give us the mid index. On a second pass, we can simply find that index and return.

Time complexity

O(n)

Space complexity

O(1)

Return to Index