changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記–Fast Slow Pointers

19. Remove Nth Node From End of List(Mediam)

移除singly linked list中從後面數來第N個node。

通常需要修改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)

快慢指針的經典題，判斷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]

給定一個array長度為N+1，其中裡面的數字從只會有[1, N]，也就是說至少會有一個重複的數字。題目說，只會有一個重複的數字，並且要找出這個數字。題目還要求不能修改array，並且使用O(1)的額外空間。

解題思路:

這題很漂亮，只少有三種解法。

  1. 因為N+1的長度，而且數字只在[1, N] 所以如果可以修改array ，那數字1放在index 0的位置，數字2放在index 1的位置，就可以找出重複的那個。
  2. 使用binary search。參考這邊的解法。
  3. 使用bit manipulation。連結
  4. 使用slow fast pointer，這邊主要討論這個解法。

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

cyclic map

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

因為從原點->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。
```cpp=
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]

給定一個array長度為N+1，其中裡面的數字從只會有[1, N]，也就是說至少會有一個重複的數字。題目說，只會有一個重複的數字，並且要找出這個數字。題目還要求不能修改array，並且使用O(1)的額外空間。

解題思路:

這題很漂亮，只少有三種解法。

  1. 因為N+1的長度，而且數字只在[1, N] 所以如果可以修改array ，那數字1放在index 0的位置，數字2放在index 1的位置，就可以找出重複的那個。
  2. 使用binary search。參考這邊的解法。
  3. 使用bit manipulation。連結
  4. 使用slow fast pointer，這邊主要討論這個解法。

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

cyclic map

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

因為從原點->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 刷題
Select a repo