找链表的中间结点和倒数第k个结点(链表笔试题面试题)
一、问题
公司主营业务:成都网站建设、做网站、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出宁德免费做网站回馈大家。
查找链表的中间节点
查找链表的倒数第k个结点
二、解决思路:快慢指针
找中间节点:快指针走两步,慢指针走一步
找倒数第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个结点(链表笔试题面试题)
URL链接:http://scyanting.com/article/iepdjh.html