在单链表中快慢指针是一种非常经典的算法技巧通常也被称为“龟兔赛跑算法”。它的核心思想设定两个指针从同一个起点出发以不同的速度遍历链表。在链表中使用快慢指针可以快速解决查找链表的中心结点以及倒数第i个结点的问题。1. 快速查找链表的中心结点1.1 原理使用快慢指针快速查找链表中心结点的思想是是定义两个指针初始时都指向链表首元节点。慢指针slow每次走 1 步快指针fast每次走 2 步。当快指针到达链表末尾时慢指针刚好走到链表中间。1.2 代码实现使用快慢指针快速查找链表中心结点的代码实现如图1所示。图1 使用快慢指针快速查找链表中心结点的代码其中findMiddleNode()函数是自定义函数其参数head表示链表的头结点。第22-25行代码对传入的头结点进行判断如果为NULL则直接返回NULL。第27-28行定义了结点的快慢指针。第30-34行代码通过while循环设置快慢指针的位置慢指针slow每次走 1 步快指针fast每次走 2 步。当循环结束时快指针到达链表末尾慢指针正好走到链表中间。1.3 代码运行效果在main()函数中使用图2所示代码调用findMiddleNode()函数。图2 调用findMiddleNode()函数的代码代码运行效果如图3所示。图3 代码运行效果从图3中可以看出如果链表中包含奇数个结点则findMiddleNode()函数返回的是链表的中心结点如果包含偶数个结点则findMiddleNode()函数返回的偏右的中心结点。1.4 完整代码快速查找链表中心结点的完整代码如下所示。#include iostream using namespace std; /* 在单链表中快慢指针Fast and Slow Pointers是一种非常经典的算法技巧通常也被称为“龟兔赛跑算法”。 它的核心思想设定两个指针从同一个起点出发以不同的速度遍历链表。 慢指针Slow每次移动 1 步slow slow-next。 快指针Fast每次移动 2 步fast fast-next-next。 */ struct Node { int data; Node* next; }; /* 查找链表的中心结点 如果链表中结点的个数为偶数则返回的是中心靠右的结点 */ Node* findMiddleNode(Node* head) { if (head NULL) { return NULL; } Node* slow head; Node* fast head; while(fast!NULL fast-next ! NULL)//注意循环条件 { slow slow-next; fast fast-next-next; } return slow; } Node *head, *p, *r;//r表示当前链表的尾结点p表示当前结点 int x; int main() { head new Node; r head; head-next NULL; cinx; while(x ! -1) { p new Node; p-data x; p-next NULL; r-next p; r p; cinx; } Node* mid findMiddleNode(head-next); if(mid!NULL) { coutmid-data; } return 0; }
