快慢指针

快慢指针

定义：快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

应用：1、判断单链表是否为循环链表

           2、在有序链表中寻找中间元素

下面我们分别来看这两种情况：

1、A指针走一步，B指针走两步，A=B时，该链表为循环链表

初始化为：

等走到A=B时，A和B都走了三步，但A经过三个结点，B经过六个结点

根据这个过程，我们来看一下代码：

void if_CircleLinkList(LinkLIst *L){
	Node *A=L;//快指针
	Node *B=L;//慢指针
	A=A->next->next;//一次走两步
	B=B->next;//一次走一步
	while(1){
		if(A==NULL||A->next==NULL){//以NULL结尾不是循环链表
			return false;
		}else if(A==B||A->next==B){//链表中结点个数奇偶不确定
			return true;
		}else{
			A=A->next->next;
			B=B->next;
		}
	}
}

2、在一个位置长度的链表里，如何获取它的中间元素？

假设我们初始化了四个元素，通过快慢指针来查找一下中位数。

根据下列代码，我们来挪动指针试试：

void findMid(LinkLIst *L){//结构体指针
	Node *A=L;//慢指针
	Node *B=L;//快指针
	while(1){
		if(B->next==NULL){//B是最后一个结点或链表为空
			break;
		}else if(B->next->next==NULL){//B是倒数第二个元素（元素个数为奇数）
			A=A->Next;
			break;
		}
		B=B->next->next;
		A=A->next;
	}
	printf("%d",A->data);
}

①

②

此时，2和3为中间元素，如果求中位数的话，可以选择返回两个数的和的一半，我们找的是中间元素，可以返回2和3。而如果我们有五个元素的话，

3就是该链表的中间元素。

注意：在求中位数时，要看 算结点个数的时候有没有加头结点，我们这种方法没有加头结点。