描述：
輸入兩個無環的單鏈表，找出它們的第一個公共結點，（注意因為傳入資料是鏈表，所以錯誤測驗資料的提示是用其他方式顯示的，保證傳入資料是正確的）
(題目來自牛客網)
用C++實作如下
/*
struct ListNode { //定義鏈表結構，val和ListNode*
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//
//思路,使用雙指標法來求解，兩個鏈表公共節點前的長度值相加是固定的，所以對于每一個鏈表
//，跑完自己后接上對方頭，兩個鏈表同樣操作后會在第一公共結點處相遇
ListNode *q1=pHead1, *q2=pHead2; //定義q1,q2兩個鏈表指向頭
if(q1==NULL || q2==NULL) //q1為空,或者q2為空,回傳空
return NULL;
while(q1!=q2) //當兩者不相等時
{
q1=q1->next;
q2=q2->next; //節點依次往后移動
if(q1!=q2) //防止q1和q2的next都是空時進入無窮無盡的回圈
{
if(q1==NULL)
q1=pHead2; //一個鏈表為空時,接上另一個鏈表
if(q2==NULL)
q2=pHead1; //一個鏈表為空時,接上另一個鏈表
}
}
return q1; //回傳公共節點q1
}
};
純手撕代碼，如果覺得內容不錯麻煩點個贊，后面陸續配上Top100演算法題通俗易懂的講解視頻，可以花兩個月時間完全掌握，進大廠不是夢，轉行狗親測！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287485.html
標籤：其他
上一篇：C++試題精選----類的封裝和繼承----NO.2
下一篇：成像代碼讀入部分