【百度算法题】找出两个单向链表的交点

1. 简介

面试题：找出两个单向链表的交点。

问题说明：
给出两个单向链表的第一个元素，找出它们的交点，如果没有交点则返回null，如果有多个则返回第一个。

2. 问题分析

这个问题中，要求使用的是单向链表，那么我们回忆下单向链表的特性，有如下几点：

1) 每一个结点包含有下一个结点的引用 next
2) 遍历的顺序只能是从链表的首部回到尾部，无法反向遍历
3) 无法之间获取到它的长度值
4) 最后一个结点的next 指针是 null

然后我们分析下这个问题。

根据上文性质1可知：两个单向链表如果相交的话，那么肯定不会像两条直线相交一样的X 型，而应该是Y 型，如下图：

也就是说，两个单向链表一旦有交点，那么它们的最后一个结点一定也是他们的交点。

3. 解题思路

有了以上的简单分析，接下来我们研究下解体思路。

既然，有交点的两个单向链表的结尾一定是交点，那么我们可以先分别遍历到两个链表的尾部，check 下它们的尾部是否是相等的。

如果尾部相等的话，然后接下来的问题是，如何找到第一个交点呢？我们看下下面的图：

如果能获取到这个等长点的位置的话，那么可以从这个结点开始，对两个链表同时进行遍历，当两个结点第一次相等的时候，这个结点就是两个链表的首个交点。

然后，怎么找到这个等长点呢？这个比较简单，可以获取到两个链表的分别的长度，先行让较长的那个链表往后遍历差值的步骤就可以找到了。

那么，根据上面的分析，我们梳理下这个这个解题的步骤：
1) 分别遍历两个链表，获取到两个链表尾部结点；如果尾部结点相等的话，证明两个链表有交点
2) 在遍历的同时，通过计数获取到的长度 length1 和 length2；
3) 较长的链表先遍历到 |length1 - langth2| 的位置；
4) 然后再同时遍历两个链表，并判断它们的当前结点是否相等，相等的话，则这个结点就是交点；

4. 实现

有了以上的分析，接下来我们写一下实现，这里我用Java语言来写

//定义下数据结构
class LNode {
    // 下一个结点
    LNode next;
}
public static LNode findIntersection(LNode a, LNode b) {
    // 定义用于存放尾结点和链表长度的变量
    LNode lastOfA, lastOfB;
    int lengthA, lengthB;
    
    // 找到 a 的尾结点 和长度
    LNode tmp = a;
    while(tmp != null && tmp.next != null) {
        lastOfA = tmp;
        lengthA++;
        
        tmp = tmp.next;
    }
    
    // 找到b的 的尾结点 和长度
    tmp = b;
    while(tmp != null && tmp.next != null) {
        lastOfB = tmp;
        lengthB++;
        
        tmp = tmp.next;
    }
    
    if (!(lastOfA.equals(lastOfB))) {
        // 没有交点
        return null;
    }
    
    int x = lengthA - lengthB;
    // 取绝对值
    int step = Math.abs(x);
    
    // 把较长的先行遍历
    if (x >= 0) {
        for (int i=0; i<step; i++) {
           a = a.next;
        }
    }else {
        for (int i=0; i<step; i++) {
           b = b.next;
        }
    }
    
    // 同时遍历
    LNode tmpa = a;
    LNode tmpb = b;
    while (tmpa != null && tmpb != null) {
        if (tmpa.equals(tmpb)) {
            // 相等的话这个就是交点
            return tmpa;
        }
        
        tmpa = tmpa.next;
        tmpb = tmpb.next;
    }
    return null;
}

以上，就是简单的Java实现（我没有太仔细调试，只是写出了大概的流程）

从上面的代码分析，代码的时间复杂度是在O(m + n + x + y) ，其中：
m - A链表的长度
n - B链表的长度
x - A和B的长度差
y - 从等长点到交点的距离

5. 另一种实现

这个问题，还有另一种比较不错的解法，这个解法的逻辑上更加简单：

1) 反转两个链表
2) 如果两个反转后的首结点不相等，则说明没有交点；
3) 同时遍历两个链表，当它们的结点的 next 不相等的时候，则说明当前的就是首个交点

这个问题里面涉及到另一个简单算法，那就是“反转单向链表”，这个问题读者可以自行研究下，这里不再赘述了。