哈希表链表双指针

题目链接：

https://leetcode.cn/problems/intersection-of-two-linked-lists/
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

方案一：

解题思路：

  • 题中说到不能通过节点的值是否相等来判断，这一点很明显是想判断引用的对象是否为同一个
  • 对于单向链表结构，没法直接 for 循环，那就上 while 循环吧
  • 判断两个链表的相同节点，即面临着两重遍历，如果嵌套 while 循环则时间复杂度会到 O(n2)

  • 为了避免嵌套循环，我自然想到用一个额外的集合先将 B 链表的节点记录下来

    解题代码：

    1. public class Solution {
    2.   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.       Set<ListNode> bSet = new HashSet<>();
    4.       ListNode temp = headB;
    5.       while (temp != null) {
    6.           bSet.add(temp);
    7.           temp = temp.next;
    8.       }
    10.       ListNode current = headA;
    11.       while (current != null) {
    12.           if (bSet.contains(current)) {
    13.               return current;
    14.           }
    15.           current = current.next;
    16.       }
    17.       return null;
    18.   }
    19. }

    运行结果：

    image.png

    复杂度分析：

  • 时间复杂度：O(n+m)

  • 空间复杂度：O(n)

    引发的思考：

    对于算法题，我还是习惯用 TDD 的方式来做，这样我可以参考题目中给的例子来构建测试用例，方便验证功能，也方便 DEBUG
    对于此题的解法没有达到题目中的进阶要求，空间复杂度还是高了些，上面的代码也是我第一时间能想到的解法，其实一开始用的是 ArrayList，发现耗时在 900+ ms，才意识到 ArrayList 的 contains 方法的时间复杂度是 O(n)，转而换成了 HashSet, 耗时立马降到了 5 ms，不过还不是最优解
    后续也看了题解中高手的答案，不得不说确实厉害，自己还需要继续努力啊~