这个题我拿到的第一个想法确实是遍历两个链表，先遍历第一个链表，在遍历内部再遍历第二个链表。这样两个for循环就可以计算出一样的结点了。剑指offer这一章讲的是算法的效率问题，所以我想这个题一定有更快捷的方法。但是我想不出什么快速的办法，o(╥﹏╥)o看了剑指offer上的解法，主要其实就一句话。两个存在共同结点的链表在共同结点后的结点全是共同结点，因为我们计算的链表是单链表。所以这两个链表的拓扑形状应该是Y型，而不是X型。开始我自己想的时候就是想成了X型，因此想了半天没想到什么方案。有了这个思路之后，想到更快捷的方法就是顺其自然的事情了。
剑指offer上提供了两种做法，首先是从后往前输出，因为链表的后半部分是一样的，但是前面却长短不一。这个剑指offer上的图画的很清楚。可是链表是一个从前向后的结构，没法从后向前输出，这个数据的特点“先进后出”，于是想到了栈。用栈做辅助结构，将链表的数据放进去，然后两个栈同时弹出相同数据，一直到找到最后一个相同的结点。这个思路听起来不错，但是最后剑指offer没有用它，我说一下原因。首先它需要两个辅助的栈的结构，增加了空间的开销来换时间的减少。实在不能说是上策。其次这个思路等于把链表里的数据放进栈里去操作，而这个题目最后返回的是链表的结点，也就是说在栈中找到了第一个相同的结点之后还要再去链表里找到，所以并不简便。
第二种做法是先求出两个链表的长度，然后根据长度把更长的链表截成和短的一样长，然后从两个链表连个指针一起走，直到遇见相同的结点。这个结点无论是思路还是做法都很新颖简便，所以答案也采用了这种方法。
1 #include<iostream> 2 using namespace std; 3 4 struct ListNode { 5 int val; 6 struct ListNode *next; 7 /* 8 ListNode(int x) : 9 val(x), next(NULL) { 10 } 11 */ 12 }; 13 class Solution { 14 public: 15 ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) { 16 int len1 = getlen(pHead1); 17 int len2 = getlen(pHead2); 18 int gap=0; 19 20 //这段不能写成if，else。因为if-else中是程序的一个小子块，这样内部定义的变量外面不能用 21 ListNode* plong = pHead1;//默认第一个长 22 ListNode* pshort = pHead2; 23 gap = len1 - len2; 24 if(len2>len1)//如果第二个长，修改值 25 { 26 ListNode* plong = pHead2; 27 ListNode* pshort = pHead1; 28 gap = len2 - len1; 29 } 30 for (int i = 0; i < gap; i++)//将两个链表拉到一样长 31 { 32 plong = plong->next; 33 } 34 while (plong != NULL&&pshort != NULL&&plong != pshort)//寻找一样的结点 35 { 36 plong = plong->next; 37 pshort = pshort->next; 38 } 39 ListNode* commonnode = plong; 40 return commonnode; 41 } 42 int getlen(ListNode* ln) 43 { 44 if (ln == NULL) 45 return 0; 46 int count = 0; 47 while (ln) 48 { 49 count++; 50 ln = ln->next; 51 } 52 return count; 53 } 54 }; 55 int main() 56 { 57 Solution so; 58 ListNode common[2]; 59 common[0].val = 6; 60 common[0].next = &common[1]; 61 common[1].val = 7; 62 common[1].next = NULL; 63 64 ListNode left[3]; 65 left[0].val = 1; 66 left[0].next = &left[1]; 67 left[1].val = 2; 68 left[1].next = &left[2]; 69 left[2].val = 3; 70 left[2].next = &common[0]; 71 72 ListNode right[2]; 73 right[0].val = 4; 74 right[0].next = &right[1]; 75 right[1].val = 5; 76 right[1].next = &common[0]; 77 78 Solution solu; 79 ListNode *node = solu.FindFirstCommonNode(left, right); 80 while (node != NULL) 81 { 82 cout << node->val << " "; 83 node = node->next; 84 } 85 cout << endl; 86 87 return 0; 88 }
原文：https://www.cnblogs.com/neverland0718/p/11180753.html