剑指offer——两个链表的第一个公共结点---AI那点小事

概述

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

思路

首先求得两人链表的长度，并将长度大的赋给p1，小的赋给p2，长度差值为diff。之后p1向前移diff次，之后进入循环，p1与p2同时前移直到p1等于p2。

C++ AC代码#include <iostream> using namespace std; struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; class Solution { public: int getLength(ListNode* list){ if(list == NULL){ return 0; } int len = 0; ListNode* p = list; while(p){ len++; p = p->next; } return len; } ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { if(pHead1 == NULL || pHead2 == NULL){ return NULL; } int len1 = this->getLength(pHead1); int len2 = this->getLength(pHead2); ListNode* p1 = (len1>len2)?pHead1:pHead2; ListNode* p2 = (len1>len2)?pHead2:pHead1; int diff = (len1>len2)?len1-len2:len2-len1; for(int i = 0 ; i < diff ; i++){ p1 = p1->next; } while(p1 != p2){ p1 = p1->next; p2 = p2->next; } return p1; } }; ---来自腾讯云社区的---AI那点小事