剑指Offer - 九度1505 - 两个链表的第一个公共结点
2013-11-24 20:09
- 题目描述：
-
输入两个链表，找出它们的第一个公共结点。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的两个链表的元素的个数。
接下来的两行，第一行为第一个链表的所有元素，中间用空格隔开。第二行为第二个链表的所有元素，中间用空格隔开。
- 输出：
-
对应每个测试案例，
输出两个链表的第一个公共结点的值。
如果两个链表没有公共结点，则输出“My God”。
- 样例输入：
-
5 4
1 2 3 6 7
4 5 6 7
3 3
1 5 7
2 4 7
2 3
1 3
4 5 6
- 样例输出：
-
6
7
My God
题意分析：
给定两条链表，如果有公共节点的话，请找出，否则打印“My God”。这题本身出的有问题，如果两条单链表有一个公共节点的话，那应该指的是共用同一个节点，即指向同一个内存地址。如果两链表相交于一点，那么之后的部分都完全一样了。这题由于输入的数据是两组单独的数据，因此构造出来的两条链表在内存的范畴上肯定是不相交的。只能判断两者尾巴上的数据是否一致。
下面是思路：对于长度为m，n的两条链表，如果相交于某一点，那么之后的所有数据都必须一一相等。因此定义指针p1、p2指向链表1和2的表头，先将较长链表的指针移动到与短链表对齐的位置。然后逐个检查两两节点是否相等。如果当前节点相等，则表示此节点可能是“第一个公共节点”，然后从此节点往后移动逐个检查后面的节点是否全部对应相等。如果全部相等，则此节点就是公共节点，否则不相等的节点往后一个开始继续找答案。
这题的问题在于俩链表的公共节点应该是内存地址相同，而不是值相等。否则也就不好定义“公共”了。
// 654279 zhuli19901106 1505 Accepted 点击此处查看所有case的执行结果 1024KB 2044B 70MS
//
#include <cstdio>
using namespace std; struct ListNode{
int val;
struct ListNode *next;
ListNode(int _val = ): val(_val), next(NULL){}
}; void delete_list(ListNode *head)
{
if(head == NULL){
return;
} ListNode *ptr; while(head != NULL){
ptr = head;
head = head->next;
delete ptr;
}
} int main()
{
ListNode *h1, *h2, *p1, *p2, *cp1, *cp2;
int m, n;
int tmp;
int i; while(scanf("%d%d", &m, &n) == ){
h1 = h2 = NULL;
p1 = p2 = NULL;
for(i = ; i < m; ++i){
scanf("%d", &tmp);
if(p1 == NULL){
h1 = new ListNode(tmp);
p1 = h1;
}else{
p1->next = new ListNode(tmp);
p1 = p1->next;
}
}
for(i = ; i < n; ++i){
scanf("%d", &tmp);
if(p2 == NULL){
h2 = new ListNode(tmp);
p2 = h2;
}else{
p2->next = new ListNode(tmp);
p2 = p2->next;
}
} if(h1 == NULL || h2 == NULL){
printf("My God\n");
}else{
p1 = h1;
p2 = h2;
if(m < n){
for(i = ; i < n - m; ++i){
p2 = p2->next;
}
}else{
for(i = ; i < m - n; ++i){
p1 = p1->next;
}
} while(p1 != NULL && p2 != NULL && p1->val != p2->val){
p1 = p1->next;
p2 = p2->next;
}
/*
cp1 = p1;
cp2 = p2;
while(cp1 != NULL && cp2 != NULL){
if(cp1->val != cp2->val){
break;
}else{
cp1 = cp1->next;
cp2 = cp2->next;
}
}
if(cp1 != NULL && cp2 != NULL){
// mismatch found here, move forward
p1 = cp1->next;
p2 = cp2->next;
}else{
break;
}
*/ if(p1 != NULL && p2 != NULL && p1->val == p2->val){
printf("%d\n", p1->val);
}else{
printf("My God\n");
}
} delete_list(h1);
h1 = NULL;
delete_list(h2);
h2 = NULL;
} return ;
}