160. 相交链表（简单）

今天药忘吃喽~ 2022-09-09 06:46 132阅读 0赞

Leetcode链接：[160. 相交链表][160.]

### 题目描述： ###

> 给你两个单链表的头节点 `headA` 和 `headB` ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 `null` 。  
>   
>   
> 图示两个链表在节点 c1 开始相交：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16]

题目数据 保证 整个链式结构中不存在环。

**注意**，函数返回结果后，链表必须 **保持其原始结构** 。

示例 1：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 1]

> 输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
> 输出：Intersected at ‘8’  
> 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。  
> 从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。  
> 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_16_color_FFFFFF_t_70_g_se_x_16]

> 输入：intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
> 输出：Intersected at ‘2’  
> 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。  
> 从各自的表头开始算起，链表 A 为 \[0,9,1,2,4\]，链表 B 为 \[3,2,4\]。  
> 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_10_color_FFFFFF_t_70_g_se_x_16]

> 输入：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 。

提示：

> listA 中节点数目为 m  
> listB 中节点数目为 n  
> 0 <= m, n <= 3 \* 104  
> 1 <= Node.val <= 105  
> 0 <= skipA <= m  
> 0 <= skipB <= n  
> 如果 listA 和 listB **没有交点**，intersectVal 为 0  
> 如果 listA 和 listB **有交点**，`intersectVal == listA[skipA + 1] == listB[skipB + 1]`

进阶：你能否设计一个时间复杂度 `O(n)` 、仅用 `O(1)` 内存的解决方案？

### 源码 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            ListNode currA = headA;
            ListNode currB = headB;
    
            while(currA != currB){
        
                currA = currA != null ? currA.next : headB;
                currB = currB != null ? currB.next : headA;
            }
    
            return currA;
        }
    }

[160.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8123e0c47918477da4d34bb6fdadbcbd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/b57aa6a9978d468f9c823b4d666692db.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/cc22ca3f5e5e4d1cb14f75161748bb83.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3b684630074b48dfa840060bf5b48ca7.png