当前位置：首页 > news >正文

【LeetCode】算法详解#11 ---相交链表

news 2025/8/2 5:59:16

1.题目介绍

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

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

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

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

提示：

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

2.解决思路

这道题要求我们寻找链表相交的结点。实际上相交指的是节点地址相同，所以在判断相交时不能靠节点中的value，而是直接比较节点的物理地址。同时由题意可知，两根链表自相交开始，后面的所有节点都重合，所以我们只需要找到第一个重合的节点即可。为了完成这个需求，可以想到两种方案。

第一种，我们可以将其中一个链表每个节点都存入hash集合中，然后按照顺序让另一个链表依次判断节点是否在哈希集合中存在，即可找到链表相交的位置。该做法时间复杂度O(m+n),空间复杂度O(m)

另一种方案是让两个链表同时进行遍历，利用双指针判断链表是否相交。原理如下：利用两个指针tempA和tempB让两个链表同时开始遍历，每次遍历都判断两个节点是否相同，否则继续遍历下一个节点，当遍历到链表末尾时，下次将该指针指向另一个链表的头结点(例如tempA遍历完成链表A后指向链表B的头结点)。同理另一个指针tempB类似。在相交的情况下，假设链表A在相交前的节点数为a，相交后的节点数为c；链表b相交前节点数为b，相交后节点数为c。如果a=b，则两个链表会同时相交。如果a！=b (a<b),那么tempA在遍历完后转到链表b，再遍历b次后会与tempB指向同一个节点。

证明： tempA遍历完链表a后，此时tempB位于链表b的b+c-(a+c) = b-a。

当tempB遍历完链表b后，此时tempA位于链表b的 b-a

当两者再次遍历a个单位时，tempA位于链表b的b，tempB位于链表A的a

可以看到，两个指针都在对方链表的相交节点，则两者相交

一共移动了 tempA:a+c+b = tempB:b + c + a 次后两者一定相交

若两个链表不相交，则到两个指针都为null时结束

3.步骤讲解

1.定义链表

2.当链表为空时返回null

3.定义指针tempA和tempB，指向链表A、B的头结点

4.当链表节点不相交时循环遍历两个链表

5.如果当前节点不为null，则指向下一个节点，反之指向另一个链表的头结点

6.最终返回相交的节点

4.代码展示

// 链表节点private static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode getIntersectionNode(ListNode headA,ListNode headB){//链表为空时返回nullif (headA == null || headB == null) {return null;}//临时节点。用于记录链表A、B的起始节点ListNode tempA = headA;ListNode tempB = headB;//循环判断链表A、B是否相等while (headA != headB) {headA = headA == null ? tempB : headA.next;headB = headB == null ? tempA : headB.next;}//返回链表A、B相交的节点return headA;}