此处的快慢指的是每次移动的步数
比如定义一个slow和fast指针都指向第一个节点:
ListNode *slow = head; ListNode *fast = head;
slow每次走一步,fast每次走两步:
while (fast != nullptr) { slow = slow->next; fast = fast->next; }
此处代码最终的slow将指向链表的中间节点
如果链表的节点个数为奇数如:1 2 3 4 5,slow则为3
如果为偶数:1 2 3 4 5 6,则slow为第二个中间节点即为5
在纸上画一下,很容易证明上面的取得中间节点的结论
来看一个典型的快慢指针问题
判断单链表是否有环
结合生活中的场景我们不难想到:你是否有见过在一个环形跑道上赛跑的人,被猛男甩开几圈的场景。快慢指针同理,由于快指针步数比慢指针多,倘若有环,快指针必定会追上慢指针
代码如下:
bool hasCycle(ListNode* head) { if (head == NULL) { return false; } ListNode* ptr = head; ListNode* ptr2 = head->next; while (ptr != ptr2) { if (ptr2 == NULL ||ptr2->next ==NULL) {//如果把ptr2->next==NULL //放在前边则会报错 /* 原因是没有判断当前指针是否指向了一个有意义的位置。 我们只需要增加令其有意义的判断条件即可,即指针是否为NULL:*/ return false; } ptr = ptr->next; ptr2 = ptr2->next->next; } return true; }