题目

有两个单向链表, 两个链表情况如下:

1. 两个链表可能相交, 也可能不相交
2. 可能有环, 也可能无环

现给定两个链表的头节点, 若相交, 返回相交的第一个节点, 若不相交, 返回null

要求: 链表一长度N, 链表二长度M, 时间复杂度O(N+M)

思路分析

要想解决两个链表的相交问题, 可以分不同的情况来讨论:

1.若两链表均无环, 那么就只能是不相交或两链表汇于一点

这种情况, 可以遍历两个链表, 判断末尾节点是否为同一节点, 若不是则不相交, 若是, 链表一长度为40, 链表二长度为50, 令链表二先走10步, 之后两链表同步走, 相遇的点就是相交的第一个节点, 这应该不难理解, 就相当于将上图右侧的折以下.

2.若一个链表有环, 另一个无环, 则必不会相交. 因为无环链表若与有环链表相交, 则指针向后会随有环链表而有环, 破坏无环链表, 所以这种情况必不相交.

3.若两链表都有环, 则有三种情况, (1)不相交 (2)在环上相交 (3)在入环前相交 如图:

这时进行判断, 若两链表的入环节点相同, 则相交, 为图中第二中情况, 这时求相交节点, 不就可以将环去掉, 看成两个无环链表么? 这就回到了情况1, 完美.

若两链表入环节点不相同, 图中第一和第三种情况, 那么如何区分这两种结构呢? 令链表一的入环节点向后走, 若走了一圈都没遇到链表二的入环节点, 则为图中第一种情况, 若遇到了, 则为图中第三种情况, 此时返回任意一个即可.

实现

好, 基本思路有了, 下面首先判断链表是否有环, 判断的方法有很多, 如:

1. 使用两个指针, 指针A从头向后依次访问, 每到一个节点, 指针B从头查找该节点, 若两次步数不相同, 则存在环
2. 使用快慢指针, 指针A每次向后走两步, 指针B每次向后走一步, 若存在 p == q的情况, 则存在环, 此时令快指针A回到头节点, 两指针同时向后走, 每次走一步, 当第一次相遇时, 为第一个入环节点
3. 遍历链表, 每次将对象加到HashSet中, 若当某次加的时候, 发现已经加过该对象了, 则存在环(此方法对基本类型无效)

下面使用第二种方法来实现, 简单的Java代码实现:

链表是否有环完事了, 下面就是分情况来实现查找第一个相交节点的方法:

1.若两链表无环, 根据上面的思路实现代码如下:

2, 若一个链表有环,一个链表无环, 直接返回null即可

3.若两链表均有环, 根据上面思路实现代码如下:

完成, 下面用一个方法将上面的方法串起来就可以了, 主方法如下:

结束!!!

閱讀更多 牛牛的編程之路 的文章

關鍵字: 链表 相交 算法设计