# 160. Intersection of Two Linked Lists (E)

Given the heads of two singly linked-lists `headA` and `headB`, return *the node at which the two lists intersect*. If the two linked lists have no intersection at all, return `null`.

For example, the following two linked lists begin to intersect at node `c1`:

![](https://assets.leetcode.com/uploads/2021/03/05/160_statement.png)

The test cases are generated such that **there are no cycles anywhere** in the entire linked structure.

**Note** that the linked lists must **retain their original structure** after the function returns.

**Custom Judge:**

The inputs to the **judge** are given as follows (your program is **not** given these inputs):

* `intersectVal` - The value of the node where the intersection occurs. This is `0` if there is no intersected node.
* `listA` - The first linked list.
* `listB` - The second linked list.
* `skipA` - The number of nodes to skip ahead in `listA` (starting from the head) to get to the intersected node.
* `skipB` - The number of nodes to skip ahead in `listB` (starting from the head) to get to the intersected node.

### Solution:

**Version 1:**

这个题前提是两个都没有环。

给你输入两个链表的头结点 `headA` 和 `headB`，这两个链表可能存在相交。

如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

比如题目给我们举的例子，如果输入的两个链表如下图：

[![](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/4.png)](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/4.png)

那么我们的算法应该返回 `c1` 这个节点。

这个题直接的想法可能是用 `HashSet` 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

[![](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/5.jpeg)](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/5.jpeg)

如果用两个指针 `p1` 和 `p2` 分别在两条链表上前进，并不能**同时**走到公共节点，也就无法得到相交节点 `c1`。

**解决这个问题的关键是，通过某些方式，让 `p1` 和 `p2` 能够同时到达相交节点 `c1`**。

所以，我们可以让 `p1` 遍历完链表 `A` 之后开始遍历链表 `B`，让 `p2` 遍历完链表 `B` 之后开始遍历链表 `A`，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 `p1` 和 `p2` 同时进入公共部分，也就是同时到达相交节点 `c1`：

[![](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/6.jpeg)](https://labuladong.github.io/algo/images/%E9%93%BE%E8%A1%A8%E6%8A%80%E5%B7%A7/6.jpeg)

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 `c1` 节点是 null 空指针嘛，可以正确返回 null。

按照这个思路，可以写出如下代码：

```java
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}
```

这样，这道题就解决了，空间复杂度为 `O(1)`，时间复杂度为 `O(N)`。

**Version 2:**

求出 L1 L2的长度,若L1\<L2,用fast slow分别从头部开始走，L2先走（L2-L1）步，然后在一起走，直到相&#x9047;**.**

```
 public class Solution { 
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) 
   { 
        if(headA==null || headB==null) { return null; }     
        int lenA=getlen(headA);
        int lenB=getlen(headB);
        
        
        //the longer minus the difference
        if(lenA>lenB)
        {
      	  while(lenA>lenB)
      	  {
      		  headA=headA.next;
      		  lenA--;
      	  }	    	  
        }
        else
        {
      	  while(lenB>lenA)
      	  {
      		  headB=headB.next;
      		  lenB--;
      	  }
        }
        
        
        while(headA!=null)
        {
      	  if(headA==headB)
      	  {
      		  return headA;
      	  }
      	  headA=headA.next;
      	  headB=headB.next;
        }
        
        return null;
        	      
        
   }
   
   public int getlen(ListNode head)
   {
  	 if(head==null)
  	 {
  		 return 0;
  	 }
  	 
  	 int len=0;
  	 while(head!=null)
  	 {
  		 len++;
  		 head=head.next;
  	 }
  	 return len;
   }
 }
 
 
 //寻找两条链表的交点」的核心在于让 p1 和 p2 两个指针能够同时到达相交节点 c1，
 //那么可以通过预先计算两条链表的长度来做到这一点
 class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // 计算两条链表的长度
        for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
            lenA++;
        }
        for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
            lenB++;
        }
        // 让 p1 和 p2 到达尾部的距离相同
        ListNode p1 = headA, p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        // 看两个指针是否会相同，p1 == p2 时有两种情况：
        // 1、要么是两条链表不相交，他俩同时走到尾部空指针
        // 2、要么是两条链表相交，他俩走到两条链表的相交点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}
```