【题目】
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
【分析】
如果两个没有环的链表相交于某个节点，那么在这个节点之后的所有节点都是两个链表所共有的。
（1）遍历链表A，记录其长度len1，遍历链表B，记录其长度len2。
（2）按尾部对齐，如果两个链表的长度不相同，让长度更长的那个链表从头节点先遍历abs(len1-en2),这样两个链表指针指向对齐的位置。
（3）然后两个链表齐头并进，当它们相等时，就是交集的节点。
时间复杂度O(n+m)，空间复杂度O(1)
【代码】
/*------------------------------------
* 日期：2015-01-31
* 作者：SJF0115
* 题目: 160.Intersection of Two Linked Lists
* 网址：https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
* 结果：AC
* 来源：LeetCode
* 博客：
---------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len1 = 0,len2 = 0;
ListNode *pA,*pB;
pA = headA;
// 统计第一个链表节点数
while(pA){
++len1;
pA = pA->next;
}//while
pB = headB;
// 统计第一个链表节点数
while(pB){
++len2;
pB = pB->next;
}//while
pA = headA;
pB = headB;
// 长度相等且只一个节点一样
if(len1 == len2 && pA == pB){
return pA;
}//if
// pA指向长链表 pB指向短链表
if(len1 < len2){
pA = headB;
pB = headA;
}//if
// pA,Pb指向相同大小位置的节点上
int as = abs(len1- len2);
for(int i = 0;i < as;++i){
pA = pA->next;
}//while
// 比较是不是相交点
while(pA){
if(pA == pB){
return pA;
}//if
pA = pA->next;
pB = pB->next;
}//while
return nullptr;
}
};
【分析二】
双指针解法 ，时间复杂度O(n+m)，空间复杂度O(1):
维护两个指针pA和pB，初始分别指向A和B。然后让它们分别遍历整个链表，每步一个节点。
当pA到达链表末尾时，让它指向B的头节点；类似的当pB到达链表末尾时，重新指向A的头节点。
如果pA在某一点与pB相遇，则pA或pB就是交点。
所以最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。
【代码二】
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
// 有空链表肯定无交点
if(pA == nullptr || pB == nullptr){
return nullptr;
}//if
while(pA && pB){
// 交点
if(pA == pB){
return pA;
}//if
if(pA->next && pB->next){
pA = pA->next;
pB = pB->next;
}
// 到达pA末尾,pB未到达
else if(!pA->next && pB->next){
pA = headB;
pB = pB->next;
}
// 到达pB末尾,pA未到达
else if(pA->next && !pB->next){
pA = pA->next;
pB = headA;
}
// 同时到达pA,pB末尾
else{
return nullptr;
}
}//while
}
};
【分析三】
双指针解法 ，时间复杂度O(n+m)，空间复杂度O(1):
维护两个指针pA和pB，初始分别指向A和B。然后让它们分别遍历整个链表，每步一个节点。
当pA到达链表末尾时，让它指向B的头节点；类似的当pB到达链表末尾时，重新指向A的头节点。
如果pA在某一点与pB相遇，则pA或pB就是交点。
所以最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。
【代码三】
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
// 有空链表肯定无交点
if(pA == nullptr || pB == nullptr){
return nullptr;
}//if
while(pA != nullptr && pB != nullptr && pA != pB){
pA = pA->next;
pB = pB->next;
// 交点 或者 null
if(pA == pB){
return pA;
}
// 到达pA末尾
if(pA == nullptr){
pA = headB;
}//if
// 到达pB末尾
if(pB == nullptr){
pB = headA;
}//if
}//while
return pA;
}
};
