快慢指针与链表

当要求空间复杂度为O(1)，即只使用常量额外空间时，快慢指针对于处理链表中删除重复值和判断是否有环尤为重要。

快慢指针也可称为龟兔赛跑算法。

定义一个快指针，一个慢指针，它们的移动速度是不同的，根据这个速度差，我们就能完成一些工作了。

删除重复值

例题

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

思考

首先这个链表是有序链表。

也就是说，重复值是连续出现的。

定义两个指针，cur和i。

当发现当前节点和下个节点值相同时，即i->val == i->next->val。

i就不动了，启动cur指针。

cur一直移动到一个新的值为止。

然后再让i跟cur连上，即i->next = cur。

代码

//链表定义
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};

ListNode* deleteDuplicates(ListNode* head)
	{
		if (!head) return nullptr;
		ListNode* i = head;         //慢指针
		ListNode* cur = head;       //快指针
		while (i)
		{
      //&&逻辑运算符是先判断左边，如果不满足的话就不看右边直接返回false了。
			if (i->next && i->val == i->next->val)  //防止访问出界，先判断i->next是否有值
			{
				while (cur && cur->val == i->val) cur = cur->next;     //防止cur访问出界，先判断cur是不是空指针了 
        //上面这句while循环已经把cur移动到一个新的值处了
				i->next = cur;    //将i->next直接连接到cur处。（没释放中间元素）
			}
			i = i->next;
			cur = i;     //正常走的话cur跟着i一起走
		}
		return head;     //返回头指针，此时cur和i已经指向链表尾了
	}

判断是否有环

例题

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

思考

本题比较符合快慢指针的本质。

利用快慢指针的速度差可以判断链表内是否有环。

首先我们知道，如果没环的话，最终是能走到空节点的。

但如果有环的话，指针会回到原来的某个位置。

我们设定快指针速度为2，即一次走两个节点。

慢指针速度为1，即一次走一个节点。

如果有环的情况下，快指针会先到达环处。

快指针会回到慢指针的背后，往前追赶。

那么最终快指针会追上慢指针，两个指针相遇。说明这个链表中有环。

代码

bool hasCycle(ListNode* head) {
	ListNode* fastCur = head;
	ListNode* slowCur = head;
	while (fastCur != nullptr) //快指针到达空节点说明没有环
	{
		fastCur = fastCur->next;   //快指针先走
		if (fastCur) fastCur = fastCur->next;  //如果现在还没到尾巴的话再走一步
		if (fastCur == slowCur) return true;  //此时fastCur追上了slowCur，说明有环
		slowCur = slowCur->next;   //慢指针走一步
	}
	return false;
}