两个链表的第一个公共节点
思路
分析：
- 首先，让我们考虑特殊情况，如果两个链表的·长度相同，那我们定义两个指针变量cur1，cur2，使其分别指向两个表头，并让其一起对表一表二逐个遍历，如果cur1等于cur2，则可以直接返回cur1。
- 当cur1不为空时，说明两链表有公共节点，反之，当cur1为NULL，说明两链表无公共节点。
- 两个链表长度不同，显然不好进行计算。
- 因此，我们就需要采取办法使cur1和cur2处在相同位置。
方法一
- 我们可以分别求出表一和表二的长度，并算出它们的长度差count，再定义两个指针变量cur1，cur2，使其分别指向两个表头。
- 让长的链表的cur指针先走count个节点
- 最后让cur1和cur2一起每次走一个节点，当其相等时，返回cur1
方法二
- 设表一长度为A，表二长度为B，则易得：A + B = B + A
- 由上面的关系，我们定义两个指针变量cur1，cur2，使其分别指向两个表头，并让其同时每次移动一个节点
- 当cur1为空时，则下次移动时，让cur1指向表二的头，同理，当cur2为空时，则下次移动时，让cur2指向表一的头
- 相当于把整个表二接在表一前，把整个表一接在表二前，这样，两表的长度就相同了
- 如图：
- 这样，当cur1与cur2相等时，即可返回cur1
实现代码
方法一
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) { struct ListNode* cur1, *cur2; int count1 = 1,count2 = 1,count3; cur1 = pHead1; cur2 = pHead2; while(cur1) //计算表一长度 {; count1++; cur1 = cur1->next; } while(cur2) //计算表二长度 { count2++; cur2 = cur2->next; } cur1 = pHead1; //使cur1和cur2重新指向表一表二的头节点 cur2 = pHead2; count3 = fabs((double)count1 - (double)count2); //计算长度差 //让长的链表先走count3个节点 if(count1 > count2) { while(count3--) cur1 = cur1->next; } if(count1 < count2) { while(count3--) cur2 = cur2->next; } //找到第一个公共节点 while(1) { if(cur1 == cur2) return cur1; cur1 = cur1->next; cur2 = cur2->next; } }
方法二
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) { struct ListNode* cur1 = pHead1; struct ListNode* cur2 = pHead2; while(cur1 != cur2) { cur1 = cur1 ? cur1->next : pHead2; //如果cur1为空，那么cur1指向表二的头，否则cur1指向下一个节点 cur2 = cur2 ? cur2->next : pHead1; //cur2同理 } return cur1; }
