160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
Categories:
题意:
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交
题目数据 保证 整个链式结构中不存在环。
难度:
简单
示例:
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
分析:
判断相交在链表中是一项很基本, 也很重要的算法
我们可以将两个链表分别遍历并放入哈希表中去重, 但是当数组较长时会浪费许多资源
其实这道题的核心是找出第一个相交节点, 而非全部节点, 所以可以使用双指针同时遍历两个链表
大致思路如下:
- 设置两个指针分别指向两个链表的头部
- 判断是否重复, 重复即为相交
- 首先移动其中一个指针, 判断重复
- 移动另一个指针, 判断重复
- 直至某个指针为空返回false
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 定义两个指针，初始分别指向两个链表头部
// 如果任一链表为空，则不可能相交
if (headA == null || headB == null) {
return null;
}
ListNode ptrA = headA;
ListNode ptrB = headB;
// 当两个指针不相等时继续遍历
while (ptrA != ptrB) {
// 移动指针A
ptrA = ptrA == null ? headB : ptrA.next;
// 移动指针B
ptrB = ptrB == null ? headA : ptrB.next;
}
// 返回相交节点，如果不存在则返回null
return ptrA;