本博客主要記錄兩個(gè)解法：
1.求兩個(gè)單鏈表的節(jié)點(diǎn)個(gè)數(shù)，消除結(jié)點(diǎn)個(gè)數(shù)不同帶來的影響，兩個(gè)指針一起走，相遇即相交點(diǎn)。
2.數(shù)學(xué)方式求解。

一、求結(jié)點(diǎn)個(gè)數(shù)，消除結(jié)點(diǎn)個(gè)數(shù)不同帶來的影響，倆指針同步走

思路：兩個(gè)單鏈表相從相交的第一個(gè)結(jié)點(diǎn)開始，后面的結(jié)點(diǎn)都共享，所以兩個(gè)單鏈表的節(jié)點(diǎn)個(gè)數(shù)之差就是相交的結(jié)點(diǎn)之前，兩個(gè)單鏈表的結(jié)點(diǎn)個(gè)數(shù)之差，我們只需要將兩個(gè)單鏈表結(jié)點(diǎn)個(gè)數(shù)之差算出來，然后消除結(jié)點(diǎn)個(gè)數(shù)不同帶來的影響，讓p1和p2同時(shí)向后走，那么相遇的時(shí)候，即相交的第一個(gè)結(jié)點(diǎn)，如下圖：

p1和p2分別從兩個(gè)單鏈表的如下位置同時(shí)向后走，那么p1和p2相遇時(shí)的結(jié)點(diǎn)即為相交的第一個(gè)節(jié)點(diǎn)(如果不相交，那么p1和p2最終都會(huì)指向NULL)

代碼：

//不相交，返回NULL，相交返回第一個(gè)相交的結(jié)點(diǎn) ListNode* FindTheSameNode(ListNode* head1, ListNode* head2) {if (head1 == NULL || head2 == NULL)//兩個(gè)單鏈表都是空的{return NULL;}ListNode* p1 = head1;int num1 = 0;//記錄第一個(gè)單鏈表的節(jié)點(diǎn)個(gè)數(shù)ListNode* p2 = head2;int num2 = 0;//記錄第二個(gè)單鏈表的結(jié)點(diǎn)個(gè)數(shù)while (p1 != NULL)//計(jì)算第一個(gè)單鏈表的節(jié)點(diǎn)個(gè)數(shù){++num1;p1 = p1->next;}while (p2 != NULL)//計(jì)算第二個(gè)單鏈表的節(jié)點(diǎn)個(gè)數(shù){++num2;p2 = p2->next;}p1 = head1;p2 = head2;//讓p1或者p2把節(jié)點(diǎn)個(gè)數(shù)的差值的影響去除while (num1 > num2){p1 = p1->next; num1--;}while (num2 > num1){p2 = p2->next;num2--;}while (p1 != p2)//如果相交，則退出時(shí)p1 == p2，指向"相交的第一個(gè)結(jié)點(diǎn)"，如果不相交，則最后p1 == p2 == NULL{p1 = p1->next;p2 = p2->next;}return p1; }

二、數(shù)學(xué)思維

思路：
如下圖，假設(shè)相交的結(jié)點(diǎn)之前第一個(gè)單鏈表的結(jié)點(diǎn)個(gè)數(shù)為a，第二個(gè)結(jié)點(diǎn)個(gè)數(shù)為b，相交部分結(jié)點(diǎn)個(gè)數(shù)為c
那么p1（==head1）走完整個(gè)單鏈表，走的距離為：a+c
那么p2（==head2）走完整個(gè)單鏈表，走的距離為：b+c
如果我們讓p1走單鏈表的尾之后，從head2繼續(xù)向后走，p2走到單鏈表的尾之后從head1繼續(xù)向后走，那么最后p1和p2到相交的第一個(gè)結(jié)點(diǎn)一定相遇，因?yàn)樗鼈儌z這個(gè)時(shí)候走的總距離都為a+b+c+1，一起走的，所以p1和p2在單鏈表相交的第一個(gè)結(jié)點(diǎn)的位置一定相遇。如果單鏈表沒有相交，那么最后p1和p2都會(huì)指向NULL。

代碼：

ListNode* FindTheSameNode(ListNode* head1, ListNode* head2) {if (head1 == NULL || head2 == NULL){return NULL;}ListNode* p1 = head1;ListNode* p2 = head2;while (p1 != p2){p1 = p1 == NULL ? head2 : p1->next;p2 = p2 == NULL ? head1 : p2->next;}return p1;//如果head1和head2相交，則p1（p2）為第一個(gè)相交的結(jié)點(diǎn)，如果不相交，那么p1 == p2 == NULL }

總結(jié)

以上是生活随笔為你收集整理的单链表——判断两个单链表（无头节点）是否相交，如果相交，返回单链表的第一个结点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。