题目描述
输入两个链表，找出它们的第一个公共结点。
解题思路
这道题和160.intersection of two linked lists是一样的。都是求两个链表的第一个公共结点。
公共结点的样子：
剑指offer（三十六）：两个链表的第一个公共结点
上图就是一个有公共结点的例子，在公共结点之后，两个链表指针指向的地址是相同的。
这道题有两个解法。
方法一：
我们可以把两个链表拼接起来，一个phead1在前phead2在后，一个phead2在前phead1在后。这样，生成了两个相同长度的链表，那么我们只要同时遍历这两个表，就一定能找到公共结点。时间复杂度o(m n)，空间复杂度o(m n)。
方法二：
我们也可以先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点。此时，时间复杂度o(m n)，空间复杂度为o(max(m,n))。
代码实现(c 方法二)
/*
struct listnode {
int val;
struct listnode *next;
listnode(int x) :
val(x), next(null) {
}
};*/
class solution {
public:
listnode* findfirstcommonnode( listnode* phead1, listnode* phead2) {
// 如果有一个链表为空，则返回结果为空
if(phead1 == null || phead2 == null){
return null;
}
// 获得两个链表的长度
unsigned int len1 = getlistlength(phead1);
unsigned int len2 = getlistlength(phead2);
// 默认 phead1 长， phead2短，如果不是，再更改
listnode* pheadlong = phead1;
listnode* pheadshort = phead2;
int lengthdif = len1 - len2;
// 如果 phead1 比 phead2 小
if(len1 < len2){
listnode* pheadlong = phead2;
listnode* pheadshort = phead1;
int lengthdif = len2 - len1;
}
// 将长链表的前面部分去掉，使两个链表等长
for(int i = 0; i < lengthdif; i ){
pheadlong = pheadlong->next;
}
while(pheadlong != null && pheadshort != null && pheadlong != pheadshort){
pheadlong = pheadlong->next;
pheadshort = pheadshort->next;
}
return pheadlong;
}
private:
// 获得链表长度
unsigned int getlistlength(listnode* phead){
if(phead == null){
return 0;
}
unsigned int length = 1;
while(phead->next != null){
phead = phead->next;
length ;
}
return length;
}
};
代码实现(python2.7 方法一)
# -*- coding:utf-8 -*-
# class listnode:
# def __init__(self, x):
# self.val = x
# self.next = none
class solution:
def findfirstcommonnode(self, phead1, phead2):
# write code here
if phead1 == none or phead2 == none:
return none
cur1, cur2 = phead1, phead2
while cur1 != cur2:
cur1 = cur1.next if cur1 != none else phead2
cur2 = cur2.next if cur2 != none else phead1
return cur1