快慢指针

快慢指针
1.快慢指针的概念：
2.快慢指针的应用：
- 1. 判断单链表是否为循环链表
- 2. 在有序链表中寻找中位数
- 3.链表中倒数第k个节点

1.快慢指针的概念：

快慢指针就是存在两个指针，一个快指针，一个慢指针，两个指针每次移动的速度不一样，快的移动的快，慢的移动的慢。快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

2.快慢指针的应用：

1. 判断单链表是否为循环链表

如果链表是单纯的环形链表我们的代码可以是这样的：
```javascript
bool isCLinkList(List *Head)
{List  *p = Head;while(p){p = p->next;if(p == Head){return true;}}return false;
}```

但是仔细一想这种办法只能判断链表为圆形的那种环形链表，就是头尾相连的那一种。

假如我们遇到了leecode的一道题，这种方法就一定不行了：
在这里插入图片描述

像这种链表的尾节点没有指向头结点的情况，它也是一种环形链表，我们应该怎么做呢？因为它不再经过头结点了，所以我们就不能用第一种方法了。
那么快慢指针的方法就是一种特别简单的方法了：

bool hasCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode * fast = head;while (fast && fast -> next){slow = slow -> next;fast = fast -> next -> next;if (fast == slow){return true;}}return false;
}

定义两个指针，一个快指针，一个慢指针，快指针每次前进两步，慢指针每次前进一步，如果快指针追上了慢指针则说明这个链表是环形链表，如果没追上，则证明这个链表就是单链表。

快慢指针就好像两个人在赛跑，如果是在一个环形的跑道中，那么他们一直跑下去的话，快的就肯定能追上慢的，而且最少比慢的多跑了一圈。快慢指针判断环形链表就是这样的情况。

2. 在有序链表中寻找中位数

我们在看题之前先来做个游戏吧。
游戏的名字叫做烧火绳，游戏的规则是：烧一根不匀称的绳，从头烧到尾总共需要1个小时，现在有若干条材质相同的绳子，问如何用烧绳的方法来计时1个小时15分钟？
我的方法是：先取两绳，一绳一头烧，一绳两头同时烧。两头烧的绳烧完，是半小时，此时另一绳烧了一半，再烧另一头，烧完就是45分钟。烧完后再取一绳两头烧，烧完就是1小时15分。
其实，一根绳子两头烧就相当于是快指针，从一头烧就相当于慢指针，两头烧的绳子烧完的时候，一头烧的绳子烧了一半，就相当于快指针走完了，慢指针只走了一半。

所以如何在有序链表中寻找中位数呢？
我们需要定义两个指针，一个快指针，一个慢指针，因为链表为有序链表，所以我们控制快指针每次前进两步，慢指针前进一步，当快指针走到了链表的尾节点，慢指针就走到了链表的最中间了。另外此题还有一个陷阱就是：判断链表结点数量的奇偶性。如果我们的快指针移动了x次，如果达到了表尾的次数是（1 + 2x）则证明结点数量为奇数，则此时慢指针的值就是中位数。如果到达了链表的倒数第二个结点，则证明结点数量为偶数。则返回慢指针此时的值与下一个值的平均值。
代码如下：

int GetMedian(List *head)
{List *fast = *slow = head;while(fast && slow){if(fast == NULL){return slow -> data;}else if(fast -> next == NULL){return (double)(slow -> data + slow -> next -> data) / 2;}else{fast = fast -> next -> next;slow = slow -> next;}}
}

3.链表中倒数第k个节点

先看题：
在这里插入图片描述

这个题我们就可以使用快慢指针的方法，定义两个指针，想让第一个指针向前走k - 1步，然后在让快指针与慢指针同时向前移动，当快指针走到尾结点时，慢指针因为和快指针存在k - 1的距离所以此时慢指针就是倒数第k个结点。
代码如下：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){if (k == 0 || head == NULL){return NULL;}struct ListNode *p = head;struct ListNode *q = head;int i;for (i = 0; i < k - 1; i++){p = p -> next;if (p == NULL){return NULL;}}while (p -> next != NULL){q = q -> next;p = p -> next;}return q;
}