快慢指针

又称双指针。

在链表中，我们有时候需要判断链表中是否存在环，这个时候我们可以通过快慢指针来判断是否有环

判断是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *node1,*node2;
        node1 = head;
        node2 = node1;
        while(node2!=nullptr){
            for(int i=0;i<2 && node2!=nullptr;i++){
                node2 = node2 -> next;
                if(node1 == node2){
                    return true;
                }
            }
            node1 = node1->next;
        }
        return false;
    }
};

通过两个指针，一个快指针先动，慢指针后动，达到速度差，可以实现类似于套圈的效果

将链表分成两部分

1
2
3
4
5
6
7
8
9
ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }