# Leetcode刷題學習筆記--Fast Slow Pointers
### [19. Remove Nth Node From End of List(Mediam)](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
移除singly linked list中從後面數來第N個node。
:::success
通常需要修改linked list第一個node的話，可以新增一個dummy head來改。
:::

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *dummy_head = new ListNode(-1, head);
    ListNode *slow = dummy_head;
    ListNode *fast = dummy_head;
    for(int i = 0; i < n; ++i)
            fast = fast->next;
        
    while(fast->next) {
        slow = slow->next;
        fast = fast->next;
    }
        
    slow->next = slow->next->next;
        
    return dummy_head->next;     
}

### [141. Linked List Cycle(Easy)](https://leetcode.com/problems/linked-list-cycle/)
快慢指針的經典題，判斷linked list是否為cycle。
> 快指針追上慢指針，即為cycle。

bool hasCycle(ListNode *head) {
    if(!head || !head->next) return false;
    ListNode *s, *f;
    s = head;
    f = head->next;
    while(s != nullptr && f != nullptr) {
        if(s == f)
            return true;
        s = s->next;
        if(f->next)
            f = f->next->next;
        else
            return false;
    }
        
    return false;
}

### 287. [Find the Duplicate Number[Medium]](https://leetcode.com/problems/find-the-duplicate-number/)
給定一個array長度為N+1，其中裡面的數字從只會有[1, N]，也就是說至少會有一個重複的數字。題目說，只會有一個重複的數字，並且要找出這個數字。題目還要求不能修改array，並且使用O(1)的額外空間。

解題思路:
> 這題很漂亮，只少有三種解法。
> 1. 因為N+1的長度，而且數字只在[1, N] 所以==如果可以修改array== ，那數字1放在index 0的位置，數字2放在index 1的位置，就可以找出重複的那個。
> 2. 使用binary search。參考這邊的[解法](https://www.cnblogs.com/grandyang/p/4843654.html)。
> 2. 使用bit manipulation。[連結](/3VK0v_k7TpiJwtArT1otxg#287-Find-the-Duplicate-NumberMedium)
> 3. 使用slow fast pointer，這邊主要討論這個解法。

例如array nums=[1, 3, 4, 2, 2]，把數字當成是下一個要前往的目的index，就可以達到下面的有向圖。


==所以問題就變成，找出循環的那個點。== 找出循環點可以使用slow fast pointer的解法。當使用slow fast pointer會相遇在meet node。

因為從==原點->cyclic node的長度 == meet node->cyclic node的長度。==，所以可以找出cyclic node。
程式碼如下:

int findDuplicate(vector<int>& nums) {
    auto n = nums.size();
    if(n == 2) return nums[0];
    int slow{0};
    int fast = nums[slow];
    // find meet node
    while(1) {
        if(nums[slow] == nums[fast]) break;
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    int t = 0;
    slow = nums[slow];
    // find cyclic node
    while(1) {
        if(nums[t] == nums[slow]) break;
        t = nums[t];
        slow = nums[slow];
    }
        
    return nums[slow];
}

###### tags: `leetcode` `刷題`
for(int i = 0; i < n; ++i)
fast = fast->next;

while(fast->next) {
slow = slow->next;
fast = fast->next;
}

slow->next = slow->next->next;

return dummy_head->next;
}

### [141. Linked List Cycle(Easy)](https://leetcode.com/problems/linked-list-cycle/)
快慢指針的經典題，判斷linked list是否為cycle。
> 快指針追上慢指針，即為cycle。

bool hasCycle(ListNode *head) {
if(!head || !head->next) return false;
ListNode *s, *f;
s = head;
f = head->next;
while(s != nullptr && f != nullptr) {
if(s == f)
return true;
s = s->next;
if(f->next)
f = f->next->next;
else
return false;
}

return false;
}

### 287. [Find the Duplicate Number[Medium]](https://leetcode.com/problems/find-the-duplicate-number/)
給定一個array長度為N+1，其中裡面的數字從只會有[1, N]，也就是說至少會有一個重複的數字。題目說，只會有一個重複的數字，並且要找出這個數字。題目還要求不能修改array，並且使用O(1)的額外空間。

解題思路:
> 這題很漂亮，只少有三種解法。
> 1. 因為N+1的長度，而且數字只在[1, N] 所以==如果可以修改array== ，那數字1放在index 0的位置，數字2放在index 1的位置，就可以找出重複的那個。
> 2. 使用binary search。參考這邊的[解法](https://www.cnblogs.com/grandyang/p/4843654.html)。
> 2. 使用bit manipulation。[連結](/3VK0v_k7TpiJwtArT1otxg#287-Find-the-Duplicate-NumberMedium)
> 3. 使用slow fast pointer，這邊主要討論這個解法。

例如array nums=[1, 3, 4, 2, 2]，把數字當成是下一個要前往的目的index，就可以達到下面的有向圖。

![cyclic map](https://i.imgur.com/HHA03DI.png)

==所以問題就變成，找出循環的那個點。== 找出循環點可以使用slow fast pointer的解法。當使用slow fast pointer會相遇在meet node。
![meetnode](https://miro.medium.com/max/661/1*Cz21AwuLBHZgUV7JfB0yjQ.png)

因為從==原點->cyclic node的長度 == meet node->cyclic node的長度。==，所以可以找出cyclic node。
程式碼如下:

int findDuplicate(vector<int>& nums) {
auto n = nums.size();
if(n == 2) return nums[0];
int slow{0};
int fast = nums[slow];
// find meet node
while(1) {
if(nums[slow] == nums[fast]) break;
slow = nums[slow];
fast = nums[nums[fast]];
}
int t = 0;
slow = nums[slow];
// find cyclic node
while(1) {
if(nums[t] == nums[slow]) break;
t = nums[t];
slow = nums[slow];
}

return nums[slow];
}

###### tags: `leetcode` `刷題`