Intersection of Two Linked Lists
本题收获：
1.链表的输入输出
2.交叉链表：这个链表可以有交叉点，只要前一个节点的的->next相同即可。
题目：Intersection of Two Linked Lists
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.
注意：题目中两个链表是有交叉点，只要a2，b3指向的下一个节点地址都是c1的即可。
思路：
我的思路：刚开把题目理解错了，以为是两个单链表有相同的节点。
leetcode/dicuss思路：看看网上的思路
那题目的最好解法，这技巧问题阿，遍历list1 后接着遍历list2，同时，遍历list2然后遍历list1，这样两个遍历的长度是一样的O(n+m)，怎么判断相等呢？
list1: O O O O O ⑴ ⑵ ⑶
list2: □ □ □ □ ⑴ ⑵ ⑶
假如list 如上，⑴ ⑵ ⑶ 为相同的节点，那么遍历list1 这样便是这样：
O O O O O ⑴ ⑵ ⑶ □ □ □ □ ⑴ ⑵ ⑶
遍历list2 便是这样。
□ □ □ □ ⑴ ⑵ ⑶ O O O O O ⑴ ⑵ ⑶
合在一起看看：
O O O O O ⑴ ⑵ ⑶ □ □ □ □ ⑴ ⑵ ⑶
□ □ □ □ ⑴ ⑵ ⑶ O O O O O ⑴ ⑵ ⑶
好了，现在规律出来了。这个逻辑出来明显，主要麻烦是在遍历一个结束后接上第二个，直接改链表不好，所以，使用flag 控制。
算法逻辑：
- 判断list 是否有NULL 情况
- 同时遍历 两个新链表
- 如果节点地址相同，返回
- 如果不相同继续遍历
- 遍历结束返回NULL
代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA, *p2 = headB;
if(p1 == NULL || p2 == NULL)
return NULL;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
if(p1 == NULL && p2 != NULL)
p1 = headB;
if(p2 == NULL && p1 != NULL)
p2 = headA;
}
return p1;
}
};
我的测试代码：
代码1：是错误的理解，即两个单独的链表。
#include "stdafx.h"
#include "iostream"
#include "vector"
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){} //what this mean
}; class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB; if (p1 == NULL || p2 == NULL) return NULL; while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 == NULL) p1 = headB->next;
if (p2 == NULL) p2 = headA->next;
//cout << p1->val << endl;
//cur1 = cur1->next;
//cout << p2->val << endl;
//cur2 = cur2->next;
//cout << cur2->val << endl;
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1->val == p2->val) //如果是两个链表找相同点，则(p1->val ==p2->val)
{
//cout << p1 << endl;
return p1;
}
//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
// if (p1 == NULL && p2 == NULL)
{
//cur2 = headA;
//cout << "hhh" << endl;
}
}
//cout << p1 << endl;
return p1;
}
}; int _tmain(int argc, _TCHAR* argv[])
{
ListNode *h1 = new ListNode(), *h2 = new ListNode(), *p1 = NULL, *node1 = NULL, *p2 = NULL, *node2 = NULL, *head = NULL;
vector<int> nums1 = { , , , }, nums2 = { , , , , };
//nums1 = { 1, 2, 3, 4 }; //题目理解错误，条件给的出错，
//nums2 = { 0, 9, 7, 3, 4 };
p1 = h1;
p2 = h2;
for (size_t i = ; i < nums1.size(); i++)
{
node1 = new ListNode(nums1.at(i)); if (h1 == NULL)
{
h1 = node1;
}
else p1->next = node1;
p1 = node1;
} for (size_t j = ; j < nums2.size(); j++)
{
node2 = new ListNode(nums2.at(j));
if (h2 == NULL)
{
h2 = node2;
}
else p2->next = node2;
p2 = node2;
} Solution solution;
head = solution.getIntersectionNode(h1, h2);
cout << head->val << endl; //为空所以出错
system("pause");
return ;
}
代码2：正确思路代码，也可以看到这两的mian函数的区别。
#include "stdafx.h"
#include "iostream"
#include "vector"
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){} //what this mean
}; /*class MyClass
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *cur1 = headA, *cur2 = headB;
//cur1 = headA, cur1 = headB;
//cout << cur1 << endl;
if (cur1 == NULL || cur2 == NULL)
return NULL; while (cur1 != cur2)
{
//cout << cur1 << endl;
cur1 = cur1->next;
//cout << cur1->val << endl;
cur2 = cur2->next;
//cout << cur2->val << endl;
if (cur1 == NULL && cur2 != NULL)
{
//cout << cur1 << endl;
cur1 = headB;
//cout << cur1->val << endl;
}
if (cur2 == NULL && cur1 != NULL)
{
cur2 = headA;
//cout << cur2->val << endl;
}
if (cur2 == NULL && cur1 == NULL) //测试是否进入空指针
{
//cur2 = headA;
cout << "hhh" << endl;
}
}
return cur1;
//cout << cur1->val << endl;
}
};*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB; if (p1 == NULL || p2 == NULL) return NULL; while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 == NULL) p1 = headB->next;
if (p2 == NULL) p2 = headA->next;
//cout << p1->val << endl;
//cur1 = cur1->next;
//cout << p2->val << endl;
//cur2 = cur2->next;
//cout << cur2->val << endl;
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1 == p2) //如果是两个链表找相同点，则(p1->val ==p2->val)
{
//cout << p1 << endl;
return p1;
}
//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
// if (p1 == NULL && p2 == NULL)
{
//cur2 = headA;
//cout << "hhh" << endl;
}
}
//cout << p1 << endl;
return p1;
}
}; int main()
{
ListNode *head1, *head2, *node1, *node2, *node3,*node4,*node5,*head;
node1 = new ListNode(); //这样的赋值，链表就会有交叉点了，和题目一样
node2 = new ListNode();
node3 = new ListNode();
node4 = new ListNode();
node5 = new ListNode(); head1 = node1;
head1->next = node2;
node2->next = node5;
node5->next = NULL; head2 = node3;
head2->next = node4;
node4->next = node5;
node5->next = NULL; Solution solution;
head = solution.getIntersectionNode(head1, head2);
cout << head->val << endl;
system("pause");
return ;
}