微软面试题之两个链表的第一个公共结点
2023-09-14 09:10:07 时间
问题描写叙述:给定两个单向链表,找出它们的第一个公共节点。链表的节点定义例如以下:
struct ListNode { int m_nKey; ListNode* m_pNext; };
思路:
假设两个单向链表有公共的节点,也就是说两个链表从某一个节点開始。它们的m_pNext都指向同一个节点。
但因为是单向链表的节点,每一个节点仅仅有一个m_pNext,因此从第一个公共节点開始,之后它们全部的节点都是重合的。不可能出现分叉。
所以。两个有公共结点而部分重合的链表,拓扑形状看起来像一个Y,而不可能像X。
首先遍历两个链表得到它们的长度。就能知道哪个链表比較长。以及长的链表比短的链表多几个结点。在第二次遍历的时候。在较长的链表上先走若干步。接着再同一时候在两个链表上遍历。找到的第一个同样的结点就是它们的第一个公共结点。
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { //得到两个链表的长度 int len1=GetListLength(pHead1); int len2=GetListLength(pHead2); //两个链表长度差 int lenDif=len1-len2; //定义两个指针变量。分别指向长链表和短链表 ListNode *pLong=pHead1; ListNode *pShort=pHead2; if(len2>len2) { pLong=pHead2; pShort=pHead1; lenDif=len2-len1; } //先在长链表上走lenDif步 for(int i=0; i<lenDif; ++i) pLong=pLong->m_pNext; //然后同一时候遍历 while((pLong!=NULL)&&(pShort!=NULL)&&(pLong!=pShort)) { pLong=pLong->m_pNext; pShort=pShort->m_pNext; } //得到第一个公共结点 ListNode *pCommonNode=pLong; return pCommonNode; } //返回链表的长度 int GetListLength(ListNode *pHead) { int nlength=0; ListNode *pNode=pHead; while(pNode!=NULL) { nlength++; pNode=pNode->m_pNext; } return nlength; }转载请注明:http://blog.csdn.net/lsh_2013/article/details/46352507
相关文章
- 面试题系列:Java 夺命连环16问
- .NET面试题(一)
- Java实现 LeetCode 887 鸡蛋掉落(动态规划,谷歌面试题,蓝桥杯真题)
- 整理面试题
- 最新Java基础面试题及答案整理
- 75道阿里Java面试题,你能答上几道?
- (剑指Offer)面试题56:链表中环的入口结点
- (剑指Offer)面试题16:反转链表
- (剑指Offer)面试题13:在O(1)时间内删除链表结点
- (剑指Offer)面试题1:赋值运算符函数
- git常见的面试题
- (剑指Offer)面试题39:判断平衡二叉树
- (剑指Offer)面试题18:树的子结构
- (剑指Offer)面试题17:合并两个排序的链表
- (剑指Offer)面试题13:在O(1)时间内删除链表结点
- 面试题之数组的去重方式
- MySQL面试题——in是否使用【索引】
- 软件测试工程师经典面试题
- Spring常见面试题(13个面试题,回答超详细)
- 硅谷科技巨头最刁钻面试题集锦
- 面试题 08.08. 有重复字符串的排列组合-快速排序+回溯深度优先搜索
- 收集的MySQL的面试题分享给大家
- 【剑指Offer学习】【面试题26:复杂链表的复制】
- 2022年最新软件测试面试题+答案解析(每日20题,持续更新中)【二】
- 我以为自己MySQL够牛逼了,直到看到了Alibaba的面试题 | 必读篇
- 【Android】全网最详细的Android面试题合集,23求职速领
- 【2023】DevOps、SRE、运维开发面试宝典之Docker相关面试题