# Posts tagged as “fast slow”

Write an algorithm to determine if a number n is happy.

happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1


Example 2:

Input: n = 2
Output: false


Constraints:

• 1 <= n <= 231 - 1

## Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

## Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

Time complexity: O(L)
Space complexity: O(1)

## C++

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1234, and 5, the middle nodes are 0112, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.


Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.


Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 1 <= Node.val <= 105

## Solution: Fast / Slow pointers

Use fast / slow pointers to find the previous node of the middle one, then skip the middle one.

prev.next = prev.next.next

Time complexity: O(n)
Space complexity: O(1)

## C++

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln


Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …


You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]


Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]


Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

## Solution: Three steps

Step 1: Find mid node that splits the list into two halves.
Step 2: Reverse the second half
Step 3: Merge two lists

Time complexity: O(n)
Space complexity: O(1)

# Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.


Note:

Given n will always be valid.

Could you do this in one pass?

# Solution 1: Two passes

Time complexity: O(L)

Space complexity: O(1)

# Solution 2: Fast/Slow Pointers + Dummy Head / Prev

Fast pointer moves n steps first, and then slow pointer starts moving.

When fast pointer reaches tail, slow pointer is n-th node from the end.

Time complexity: O(L)

Space complexity: O(1)

# Problem

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

# Solution1: HashTable

Time complexity: O(n)

Space complexity: O(n)

# Solution2: Fast + Slow pointers

Time complexity: O(n)

Space complexity: O(1)