[数据结构与算法]数据结构学习：有关带头结点的单向链表的常见考题（c语言）

1.将链表中pp结点之后的结点原地逆置（反转）。

解题思路：
通过设置两个指针ss\ssnext指针，其中一个ss指针指向pp结点的下一个节点，将pp指针后面的结点置空，留下链表中在pp结点前的元素，再利用设置的另一指针ssnext指针保存ss指针下一结点的信息，接着将ss指向的结点插入pp结点的后面，ss指针接着再指向指向下一结点，直到ss指针为空。

//1.将链表中pp结点之后的结点原地逆置（反转）。
void ReverseList(LNode *pp)
{
	LNode *ss,*ssnext;//设置两个指针ss\ssnext。 
	
	ss=pp->next;//ss指针指向pp结点的下一个节点。 
	pp->next=NULL;//将pp指针后面的结点置空，留下链表中在pp结点前的元素。 
	
	while(ss!=NULL)
	{
		ssnext=ss->next;//ssnext指针保存ss指针下一结点的信息。 
		
		//将ss指向的结点插入pp结点的后面。 
		ss->next=pp->next;
		pp->next=ss;
        
        ss=ssnext;//ss指针接着再指向下一结点。 
	} 
}

2.反向打印链表中全部的元素。

解题思路：
利用递归实现，当指针一直没有指向表尾时，便一直调用自身函数，直到指针为空返回，便从链表结尾从后往前执行输出语句。 时间复杂度为O(n)。

//2.反向打印链表中全部的元素。
void PrintList1(LNode *pp)
{
	if(pp == NULL) return;//判断指针是否为空。 
	
	PrintList1(pp->next);//调用自身函数。 
	
	printf("%3d",pp->data);//输出语句。 
}

3.找出带头结点的单链表倒数第k(k>0)个结点。

解题思路：
可以设置两个指针，一个先出发设为fast指针，一个后出发设为slow指针,先让fast指针从表头移动到正数第k个结点，再设置另slow指针保持与先出发的指针一样的速度，向后移动，直到fast指针移动到表尾，这时slow移动的位置就是表长减去k的位置，也就是倒数第k个位置。

//3.找出带头结点的单链表倒数第k(k>0)个结点。
LNode *FindKNode(LinkList LL,unsigned int kk)
{
	LNode *fast=LL;//设置一个先出发的fast指针。 
	int ii=0;
	while((fast!=NULL)&&(ii<kk))
	{
		fast=fast->next;//fast指针移动到第k个结点。 
		ii++;
	}
	if(fast == NULL) return NULL;//当fast指针等于空时，说明表长小于k，返回空。 
	
	LNode *slow=LL->next;//设置一个后出发的slow指针。 
	while(fast!=NULL)//当fast指针移动到表尾的时候slow指针刚好移动到第k个结点位置 
	{
		slow=slow->next;
		fast=fast->next;
	}
	
	return slow; 
}

4.判断单链表是否有环，并找到环的入口。

解题思路：
思路一：
慢指针走一步，快指针走两步。快指针是慢指针速度的两倍，当快指针的路程是慢指针的两倍时，它们会相遇。
注意找环的入口的时候，需要通过计算：设从表头到环入口的距离为len，环的周长为peri，在慢指针进入环中的长度为x后与快指针相遇，快指针经过n圈环与慢指针相遇。
已知快指针的路程为两倍的慢指针的路程， 则可以得到:
len+n* peri+x=2*（len+x）整理可得：len=n*peri-x，因此在快慢指针相遇后再设置一个指针从表头出发，保持与慢指针一样的速度 ，两个指针将会在环入口相遇。
图解：

//4.判断单链表是否有环，并找到环的入口。
LNode *FindLoop(LinkList LL)
{
	LNode *fast,*slow;//设置快慢指针。 
	fast=LL;
	slow=LL;
	while(fast!=NULL)
	{
		fast=fast->next->next;//快指针fast走两步。 
		slow=slow->next;//慢指针slow走一步。 
		if(slow == fast) break;//快指针fast的路程是慢指针slow的两倍时，它们会相遇。
	} 
	if(fast == NULL) { printf("该链表没有环！\n"); return NULL; }//当快指针fast走到表尾时证明该链表没有环。 
	
	
	//寻找环的入口。 
	LNode *enter=LL;//设置一个指针指向头结点。 
	
	while(slow!=enter)
	{
		slow=slow->next;
		enter=enter->next;
	}
	
	return enter;
}

思路二：
还可以通过指针每走一步就遍历它所经过的结点，如果找到了相同的结点，那么就证明该链表具有环，且环的入口就是所找到的相同的结点。时间复杂度为O(n^2)

5.找出两个汇聚单链表的公共结点，如果没有汇聚，返回空，如果有，返回汇聚的第一个结点。

解题思路：
对于解决这道题，可以先求出两个链表长度之差n，再将较长链表的指针从头移动 n个结点，然后让较短链表的指针与较长链表的指针同时移动，直到找到汇聚点或者其中一个链表的表尾。时间复杂度为O(n)。

//5.找出两个汇聚单链表的公共结点，如果没有汇聚，返回空，如果有，返回汇聚的第一个结点。
//先写一个求链表长度的函数。
// 求链表的长度，返回值：>=0-表LL结点的个数。
int  LengthList(LinkList LL)
{
  if (LL == NULL) { printf("链表LL不存在。\n"); return 0; } // 判断链表是否存在。

  LNode *pp=LL->next;  // 从头结点的下一个节点开始。

  int length=0;

  while (pp != NULL) { pp=pp->next; length++; }

  return length;
}

LNode *FindJoin(LinkList La,LinkList Lb)
{
	int lena,lenb,len;//定义三个整型变量，分别为La,Lb链表的长度，len为两个链表长度之差。 
	lena=LengthList(La);
	lenb=LengthList(Lb);
	
	len=lena-lenb;//求出两个链表长度的差值。 
	
	while(lena>lenb&&len>0)
	{// 链表长度La>Lb的情况 
		La=La->next;
		len--;
	}
	while(lenb>lena&&len<0)
	{// 链表长度La<Lb的情况 
		Lb=Lb->next;
		len++;
	}
	
	while(La!=Lb&&La!=NULL&&Lb!=NULL)
	{
		La=La->next;
		Lb=Lb->next;
	}
	if(La == NULL||Lb == NULL) return NULL; 
	
	if(La == Lb) return La;	
}

6.将线性表L=(a1,a2,a3,…,an-2,an-1,an)变成L=(a1,an,a2,an-1,a3,an-2,…)。数据结点的个数为偶数。

题目详情：
假设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存，数据结点的个数为偶数。
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点。
最后得到线性表L=(a1,an,a2,an-1,a3,an-2,…)。
解题思路：
对于解决这道题，分为三步解答，详情见代码。

//6.将线性表L=(a1,a2,a3,...,an-2,an-1,an)变成L=(a1,an,a2,an-1,a3,an-2,...)。数据结点的个数为偶数。
void ReplaceList(LinkList LL)
{
	if(LL == NULL) return;//链表为空，退出函数。 
	
	//第一步：设置两个速度不一样的指针，其中快指针fast走两步，慢指针slow走一步。 
	LNode *fast,*slow;
	fast=LL;
	slow=LL;
	
	while(fast->next!=NULL)
	{
		fast=fast->next->next;
		slow=slow->next;
	}
	//循环过后fast停留在链表最后一个结点，slow在第n/2个结点。 
	
	//第二步：将slow指针之后的结点原地逆置。
	//如由a1,a2,a3,a4,a5,a6,a7,a8逆置成a1,a2,a3,a4,a8,a7,a6,a5 
	ReverseList(slow);//将slow后面的结点原地逆置的自定义函数。

    //第三步：将slow指针之后的结点一次插入到前面的结点中间 
    LNode *front,*back,*tmp;
    front=LL->next;//front指针指向链表第一个数据结点。 
    back=slow->next;//bcak指针指向slow指针的后一个结点 
    
    slow->next=NULL;//将链表只留下前半段，这一步很重要。 
	
	//插入操作 
	while(back!=NULL)
	{
		tmp=back->next;//用一个临时指针变量暂存back后一个结点的信息。
		
		//将back结点插入到前面的结点中。 
		back->next=front->next;
		front->next=back;
		
		back=tmp;//back指针重新指回后面的结点。 
		front=front->next->next;//将front指向下一个需要插入结点的前一个结点的位置。 如由a1,a8,a2,a3...中a1到a2。 
	}
	 
	/*
	//注意：如果使用下面这段代码进行循环将会出错，因为slow是在链表中的指针。
	LNode *pp,*tmp;
	pp=LL->next;
	slow=slow->next;
	 
	while(slow!=NULL);
	{
		tmp=slow->next;//这里相当于用tmp指向slow结点的下一结点;
		
		//下面这一步使slow结点的下一个结点插入到pp结点之后 
		slow->next=pp->next;pp->next=slow;
		
		slow=tmp;//slow指向slow的下一结点
		//也就是指向了插入到pp之后的那个结点，因此slow指针的轨迹将会不断在链表中形成环，永远不会为空。 
		pp=pp->next->next;
	}
	*/
}

参考学习视频：B站数据结构学习视频