【leetcode】两个链表的第一个重合节点

一、题目描述

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

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

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

二、 代码思路

暴力求解：

暴力两个for循环嵌套，依次比较。

哈希集合：

遍历第个表，将表节点装入hashset，然后遍历第二个表，如果hashset中有该节点，那么就有重复节点。

双指针：

定义两个指针 node1、node2 分别指向 headA 和 headB 的头节点，当两者不等时，同时移动 node1、node2 遍历两个链表，当有一个为空时，让其指向另外一个链表的头，不断移动，最终相遇，相遇节点即为相交节点。

把两个链表各自的首位拼接起来，想象成一个 ∞ 形状的跑道，两个在交叉的尾部出发，跑交叉的一圈，刚好在出发点汇合，但在这之前又经历了相同的跑道，因此相遇在结果处♥。

三、代码题解

/**
 * 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) {
        while(headA != null) {
            ListNode headBCopy = headB;
            while(headBCopy != null) {
                if(headA == headBCopy) {
                    return headA;
                }else {
                    headBCopy = headBCopy.next;
                }
            }
            headA = headA.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

双指针：

/**
 * 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 headATemp = headA;
        ListNode headBTemp = headB;
        while(headATemp !=headBTemp) {
            headATemp = headATemp == null ? headB : headATemp.next;
            headBTemp = headBTemp == null ? headA : headBTemp.next;            
        }
        return headATemp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25