189 8069 5689
今天在一本试题书上看到一些特别好的单链表面试题，大家都知道单链表容易在头节点处进行删除，在尾节点处进行插入，下面我们就来讨论一下这些面试题：
（一）删除一个非尾节点：
题目要求的是要删除一个不是尾节点的节点，要删除一个节点我们首先得知道是那个链表，是哪个节点节点，找到并且删除它。所以我们设计的函数是这样的：
void DelNotTailNode(SListNode* pos)
{
assert(pos);
SListNode* del = pos->next;
pos->data = del->data;
pos->next = del->next;
free(del);
del = NULL;
}其实实现起来也很简单，主要思想是删除pos位置的下一个节点，因为单链表只可以找到当前结点的下一个节点。
（二）找到单链表的中间节点：
题目要求只遍历一次就找到这个中间节点，可见按照我们的常规思路，先遍历一遍计数节点的总个数，然后二遍遍历直接找到节点是不行的。这就用到了单链表一个重要的概念——快慢指针。定义两个指针slow和fast，slow指针每次往后走一个节点位置，fast指针每次往后走俩个节点位置，当fast指针走到尾节点时，slow指针刚刚好走到中间节点位置；
SListNode* FindMidNode(SListNode* pHead)//pHead是链表的头节点
{
SListNode* fast = pHead;
SListNode* slow = pHead;
while (fast->next)
{
slow = slow->next;
fast = fast->next;
if (fast->next)
{
fast = fast->next;
}
else
{
break;
}
}
return slow;
}利用快慢指针可以解决很多类似的问题，比如找到单链表的第N个节点，或者判断链表是否带环等等，下面会有列子。
（三）判断一个链表是否带环，若带返回环的入口点（较难）
上面已经说过，通过快慢指针可以找到单链表中的任何节点，这也是通过验证的。那么原理上也可以判断链表是否带环：
如果带环，快慢指针一定会在某个节点处相遇。（fast一直在环里转，总有一个时刻，slow追上fast，相遇）
SListNode* WhetherRing(SListNode* pHead)//判断是否带环，若带，返回相遇节点
{
if (pHead == NULL||pHead->next == NULL)
return NULL;
SListNode* fast = pHead;
SListNode* slow = pHead;
while (fast)
{
slow = slow->next;
fast = fast->next;
if (fast)
{
fast = fast->next;
}
else
{
return NULL;//没有环
}
if (fast == slow)
{
return slow;//有环
}
}
return NULL;
}
如果链表带环的话，我们就可以求出相遇的节点。然后从相遇节点处断开带环链表，一个指针从链表投节点处开始往后遍历，一个指针从断开处往后遍历，相遇节点处就是环的入口点
SListNode* GetEnterNode(SListNode* pHead)//找到链表环入口节点在哪（重点）
{
SListNode* start = pHead;
SListNode* tmp = WhetherRing(pHead);
while (start != tmp)
{
start = start->next;
tmp = tmp->next;
}
return start;
}这就是单链表的一些面试经典题，我通过理解后和大家一起分享，希望对大家有些许帮助。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。