找链表的中间结点和倒数第k个结点（链表笔试题面试题）

一、问题

公司主营业务：成都网站建设、做网站、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出宁德免费做网站回馈大家。

1. 查找链表的中间节点

2. 查找链表的倒数第k个结点

二、解决思路：快慢指针

1. 找中间节点：快指针走两步，慢指针走一步

2. 找倒数第k个结点：快指针走k步或k-1步，然后慢指针再开始走

三、代码实现（c语言）

1.找中间结点

sListNode* FindMidNode(sListNode* pHead)

{

 sListNode* slow = pHead, *fast = pHead;

 while(fast!=NULL && fast->next!=NULL)

 {

  slow = slow->next;

  fast = fast->next->next;

 }

 return slow;

2.找倒数第k个结点

sListNode* FindKTailNode(sListNode* pHead,int k)
{
 assert(k >= 0);
 
 sListNode* fast = pHead, *slow = pHead;
 
 while(--k)    //快指针走k-1步 
 {
  if(fast->next == NULL)
   return NULL;
  fast = fast->next;
 }
 
 while(fast->next != NULL)
 {
  slow = slow->next;
  fast = fast->next;
 }
 return slow;
}

标题名称：找链表的中间结点和倒数第k个结点（链表笔试题面试题）
文章转载：http://bzwzjz.com/article/iepdjh.html