[剑指offer] 36. 两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

---

思路： 解法一： 一开始的思路是先遍历获取两个表的长度，再让较长的链表先遍历长度差个节点，此时再让两个链表同时遍历。 class Solution { int getLen(ListNode *list) { int res = 0; ListNode *p = list; while (p != NULL) { res++; p = p->next; } return res; } public: ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { int len1 = getLen(pHead1); int len2 = getLen(pHead2); ListNode *p1 = pHead1; ListNode *p2 = pHead2; if (len1 > len2) for (int i = 0; i < len1 - len2; i++) p1 = p1->next; else for (int i = 0; i < len2 - len1; i++) p2 = p2->next; while (p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } };

 

解法二： 讨论区看到的简洁解法： 假定 List1长度: a+n List2长度:b+n ，共有结点长度为n。 且 a<b，那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部 接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。 将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。 如果恰好p1==p2,那么p1就是第一个公共节点。 或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。 同理a>=b。 时间复杂度O(n+a+b) class Solution { public: ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { ListNode *p1 = pHead1; ListNode *p2 = pHead2; while (p1 != p2) { p1 = (p1 == NULL ? pHead2 : p1->next); p2 = (p2 == NULL ? pHead1 : p2->next); } return p1; } };

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10139965.html