题目描述

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回 null .

图示两个链表在节点 c1 开始相交：

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

注意,函数返回结果后,链表必须 保持其原始结构 .

解题思路

哈希表存储

判断两个链表是否相交,可以使用哈希集合存储链表节点.

首先遍历链表headA,并将链表 headA 中的每个节点加入哈希集合中.然后遍历链表 headB,对于遍历到的每个节点,判断该节点是否在哈希集合中：

如果当前节点不在哈希集合中,则继续遍历下一个节点;

如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点,返回该节点.

如果链表 headB 中的所有节点都不在哈希集合中,则两个链表不相交,返回 null.

双指针

It is essentially two pointersPA和PB分别指向headA和headB,Move both hands forward at the same time1,PA移动到A链表的末尾,Next step fromheadBstart of linked list,PB移动到B链表的末尾,Next step fromheadAstart of the linked list,up to two pointersPA==PB.I feel a bit like a playground catch-up problem in a math problem.

Put a group of pictures of the big guys：

输入输出示例

示例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

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

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

代码

哈希表存储

/**
 * 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) {
        Set<ListNode> hashset = new HashSet<>();
        ListNode tem = headA;
        while(tem != null){
            hashset.add(tem);
            tem = tem.next;
        }
        tem = headB;
        while(tem != null){
            if(hashset.contains(tem)){
                return tem;
            }
            tem = tem.next;
        }
        return null;
    }
}

双指针

/**
 * 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) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}