160. 相交链表（Python）

难度：★★☆☆☆

类型：链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.

在返回结果后，两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

这道题与 【题目141. 环形链表】 属于同一题型，环形链表可以使用快慢指针判断，这里我们同样使用双指针进行判别，不过步长都是一步，让两个指针分别从两个链表头结点开始向后移动，当其中一个指针走到链表末尾后，换到另一个链表的头结点上，另一个指针也是如此，这样如果两个链表相交，则一定可以相遇，且根据数量关系可知，首次相遇的结点即为相交结点。

如有疑问或建议，欢迎评论区留言~

（1）思路分析：

使用蛮力法：遍历第一个链表，将第一个链表中的每个节点都和第二个链表中的每个节点比较，如果出现相等的节点时，即为相交节点。时间复杂度：O(mn)

使用散列表：遍历第一个链表，将第一个链表中的每个节点都存入散列表中。再次遍历第二个链表，对于第二个链表中的每个节点均检查是否已经存在于散列表中，如果存在则说明该节点为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

使用栈求解：定义两个栈分别存储两个链表。分别遍历两个链表并压入到对应的栈中。比较两个栈的栈顶元素，如果二者相等则将该栈顶元素存储到临时变量中，并d出两个栈的栈顶元素。重复上述 *** 作一直到两个栈的栈顶元素不相等为止。最后存储的的临时变量即为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

分别获得两个链表的长度，计算出两个链表的长度差d，较长的链表首先移动d步，然后两个链表同时向表尾移动，当出现两个节点相同时即为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

（2）示例代码：

package cn.zifangsky.linkedlist.questions

import java.util.HashMap

import java.util.Map

import org.junit.Test

import cn.zifangsky.linkedlist.SinglyNode

import cn.zifangsky.linkedlist.SinglyNodeOperations

/**

 * 找出两个相交链表的交点

 * @author zifangsky

 *

 */

public class Question12 {

/**

 * 思路：使用散列表求解

 * @时间复杂度 O(m) + O(n) = O(max(m,n))，即：O(m)或O(n)

 * @param headNode

 * @return

 */

public SinglyNode<Integer> findIntersection1(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){

Map<Integer,SinglyNode<Integer>> nodeMap = new HashMap<>()

for(int i=1headNode1!=nulli++){

nodeMap.put(i, headNode1)

headNode1 = headNode1.getNext()

}

while (headNode2 != null) {

if(nodeMap.containsValue(headNode2)){

return headNode2

}else{

headNode2 = headNode2.getNext()

}

}

return null

}

/**

 * 思路：1，分别获得两个链表的长度；2，计算出两个链表的长度差d；

 *  3，较长的链表首先移动d步，然后两个链表同时向表尾移动

 *  4，当出现两个节点相同时即为交点

 * @时间复杂度 O(m) + O(n) + O(1) + O(d) + O(min(m,n)) = O(max(m,n))

 * @param headNode1

 * @param headNode2

 * @return

 */

public SinglyNode<Integer> findIntersection2(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){

int length1 = 0,length2 = 0 //两个链表节点数

int diff = 0

SinglyNode<Integer> temp1 = headNode1,temp2 = headNode2

//1

while (temp1 != null) {

length1++

temp1 = temp1.getNext()

}

while (temp2 != null) {

length2++

temp2 = temp2.getNext()

}

//2、3

if(length1 > 0 && length2 > 0 && length2 >= length1){

diff = length2 - length1

for(int i=1i<=diffi++){

headNode2 = headNode2.getNext()

}

}else if(length1 > 0 && length2 > 0 && length2 < length1){

diff = length1 - length2

for(int i=1i<=diffi++){

headNode1 = headNode1.getNext()

}

}else{

return null

}

//4

while(headNode1 != null && headNode2 != null){

if(headNode1 == headNode2){

return headNode1

}else{

headNode1 = headNode1.getNext()

headNode2 = headNode2.getNext()

}

}

return null

}

@Test

public void testMethods(){

//人为构造两个相交的链表 

SinglyNode<Integer> a = new SinglyNode<Integer>(11)

SinglyNode<Integer> b = new SinglyNode<Integer>(22)

SinglyNode<Integer> currentA = a,currentB = b

for(int i=3i<=8i++){

SinglyNode<Integer> tmpNode = new SinglyNode<Integer>(11 * i)

if(i < 7){

if(i%2 == 0){

currentB.setNext(tmpNode)

currentB = tmpNode

SinglyNode<Integer> tmpNode2 = new SinglyNode<Integer>(11 * i + 1)

currentB.setNext(tmpNode2)

currentB = tmpNode2

}else{

currentA.setNext(tmpNode)

currentA = tmpNode

}

}else{

currentB.setNext(tmpNode)

currentB = tmpNode

currentA.setNext(tmpNode)

currentA = tmpNode

}

}

//遍历初始链表

System.out.print("A: ")

SinglyNodeOperations.print(a)

System.out.print("B: ")

SinglyNodeOperations.print(b)

System.out.println("方法一，其交点是: " + findIntersection1(a,b))

System.out.println("方法二，其交点是: " + findIntersection2(a,b))

}

}

测试代码输出如下：

A: 11 33 55 77 88 

B: 22 44 45 66 67 77 88 

方法一，其交点是: SinglyNode [data=77]

方法二，其交点是: SinglyNode [data=77]

附：单向链表SinglyNode的定义：

package cn.zifangsky.linkedlist

/**

 * 单链表的定义

 * 

 * @author zifangsky

 * @param <K>

 */

public class SinglyNode<K extends Object> {

private K data // 数据

private SinglyNode<K> next // 该节点的下个节点

public SinglyNode(K data) {

this.data = data

}

public SinglyNode(K data, SinglyNode<K> next) {

this.data = data

this.next = next

}

public K getData() {

return data

}

public void setData(K data) {

this.data = data

}

public SinglyNode<K> getNext() {

return next

}

public void setNext(SinglyNode<K> next) {

this.next = next

}

@Override

public String toString() {

return "SinglyNode [data=" + data + "]"

}

}

链表1,2均没有环

把链表1首尾相连,判断链表2是否有环,若有环,则相交.

基本思路2：

遍遍历链表1,2,若尾指针相等,则相交.

链表1和链表2的长度想减求绝对值,较长的链表先移动差值个位置,然后两个链表同时移动,相等的地方即为交点.算法也不给出了

---