1. 返回链表的中间节点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
分析：
快慢指针同时指向头节点，快指针走两步，慢指针走一步
如果长度为偶数，那么快指针为NULL的时候停止，长度为奇数，fast->next为NULL的时候停止
慢指针指向的位置就是中间节点了
按照这种思路，实现代码如下：
LinkNode *findMidNode(LinkNode *head)
{
LinkNode *fast = head;
LinkNode *slow = head;
while(NULL!= fast &&NULL!= fast->next )
{
fast = fast->next->next;
slow = slow->next;
}
returnslow;
}
2.链表的中间节点
输入一个单向链表，输出该链表中倒数第k个结点。为符合计数习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例子
如：一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
分析：
定义两个指针，指针移动一个快，一个慢(链表的长度l)
1.快慢指针同时指向头结点
2.首先快指针移动k-1步，先走到第k个节点
3.快慢指针同时移动，直到快指针指向末尾，这时，快慢指针都走了l-k，
4.慢指针指向的节点即为我们需要寻找的节点
参考代码实现如下：
LinkNode *FindKthToTail(LinkNode *head,unsignedintk)
{
if(NULL == head || 0 == k)
return head;
LinkNode *pFast = head;
LinkNode *pSlow = head;
unsigned int i = 0;
//快指针先移动
while(i < k -1)
{
if(NULL != pFast)
{
pFast = pFast->next;
}
//k大于链表的长度
else
{
return NULL;
}
i++;
}
//快慢指针一起移动
while(NULL != pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}
3.判断链表是否有环
如何判断一个单链表是否有环？若有环，如何找出环的入口节点。
按照快慢指针的思路，使用两个指针，一个指针每次走一步，另一个每次走两步，如果链表有环，那么它们终将相遇，而如果没有环，快的指针最后会指向NULL。
按照这种思路，我们的参考代码如下：
//0:无环，1：有环
int hasLoop(LinkNode *head)
{
if(NULL == head)
return 0;
LinkNode *slow = head;
LinkNode *fast = head->next;
//当快指针到末尾时，无环，结束
while (NULL != fast && NULL != slow)
{
//快慢相遇，有环
if (fast == slow)
return 1;
slow = slow->next; // 慢指针每次走一步
fast = fast->next;
if (fast != NULL)
fast = fast->next;
}
return 0;
}
网友评论