题目地址(02.07. 链表相交)

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

题目描述

  1. 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
  3. 图示两个链表在节点 c1 开始相交：
  5. 题目数据 保证 整个链式结构中不存在环。
  7. 注意，函数返回结果后，链表必须 保持其原始结构 。
  11. 示例 1：
  13. 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
  14. 输出：Intersected at '8'
  15. 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
  16. 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
  17. 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
  20. 示例 2：
  22. 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
  23. 输出：Intersected at '2'
  24. 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
  25. 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
  26. 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
  29. 示例 3：
  31. 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
  32. 输出：null
  33. 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
  34. 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
  35. 这两个链表不相交，因此返回 null 。
  40. 提示：
  42. listA 中节点数目为 m
  43. listB 中节点数目为 n
  44. 0 <= m, n <= 3 * 104
  45. 1 <= Node.val <= 105
  46. 0 <= skipA <= m
  47. 0 <= skipB <= n
  48. 如果 listA 和 listB 没有交点，intersectVal 为 0
  49. 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
  53. 进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

前置知识


公司

  • 暂无

思路

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
image.png
将两个列表的后端对其 然后依次往后遍历curab 如果相等就返回 不等就往后走

关键点

  • 简单来说，就是求两个链表交点节点的指针

代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for singly-linked list.
  4.  * public class ListNode {
  5.  *     int val;
  6.  *     ListNode next;
  7.  *     ListNode(int x) {
  8.  *         val = x;
  9.  *         next = null;
  10.  *     }
  11.  * }
  12.  */
  13. public class Solution {
  14.         public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  15.             //定义curab两个节点
  16.             ListNode curA = headA;
  17.             ListNode curB = headB;
  18.             //定义两个列表的长度
  19.             int lenA = 0,lenB = 0;
  20.             //求ab的len
  21.             while (curA != null) {
  22.                 lenA++;
  23.                 curA = curA.next;
  24.             }
  25.             while (curB != null) {
  26.                 lenB++;
  27.                 curB = curB.next;
  28.             }
  29.             //将curab复位
  30.             curA = headA;
  31.             curB = headB;
  32.             //如果B的长度大于a 交换ab的位置和长度
  33.             if (lenB > lenA) {
  34.                 int tempLen = lenA;
  35.                 lenA = lenB;
  36.                 lenB = tempLen;
  37.                 ListNode tempCur = curA;
  38.                 curA = curB;
  39.                 curB = tempCur;
  40.             }
  41.             //ab len的长度
  42.             int difference = lenA - lenB;
  43.             //让a往前走差值的长度
  44.             while (difference-- > 0) {
  45.                 curA = curA.next;
  46.             }
  47.             //当cura不等于空的时候 判断a是否等于b 如果等于 即找到了两个列表的交点
  48.             //如果没找到 就让ab往前走一步
  49.             while (curA != null) {
  50.                 if (curA == curB) {
  51.                     return curA;
  52.                 }
  53.                 curA = curA.next;
  54.                 curB = curB.next;
  55.             }
  56.             //如果最后都没有得到交点 返回null
  57.             return null;
  58.         }
  59.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：02.07. 链表相交(2) - 图2
  • 空间复杂度：02.07. 链表相交(2) - 图3#card=math&code=O%281%29&id=uI9cw)