题⽬描述

输⼊两个链表，找出它们的第⼀个公共结点。（注意因为传⼊数据是链表，所以错误测试数据的提示是⽤其他⽅式显示的，保证传⼊数据是正确的）

思路及解答

HashSet包含法

第⼀种做法，直接依赖于 HashSet，遍历第⼀个链表的时候，将所有的节点，添加到 hashset 中，

遍历第⼆个链表的时候直接判断是否包含即可，属于空间换时间的做法。

  • ​时间复杂度​：O(m+n)，需要遍历两个链表各一次

  • ​空间复杂度​：O(min(m,n))，存储较短链表的节点

双栈法

利用栈的后进先出特性，从链表尾部开始比较，找到最后一个相同的节点。公共节点之后的节点都是相同的，所以从后往前比较，最后一个相同的节点就是第一个公共节点

  • 时间复杂度​：O(m+n)，需要遍历两个链表各两次（压栈和出栈）

  • ​空间复杂度​：O(m+n)，需要两个栈存储所有节点

长度差法（推荐）

可以将两个链表想象为两段路程，公共节点是终点。让长的链表先走多出的距离，然后同时前进，就能同时到达公共节点

譬如现在有⼀个链表 1->2->3->6->7，另外⼀个链表 4->5->6->7，明显可以看出第⼀个公共节点是6 。 最直接的⽅法，每⼀个链表都遍历⼀次，计算链表中的个数，⽐如 1->2->3->6->7 个数为5， 4->5->6->7 个数为4，两者相差1（设为k）个。

我们可以使⽤两个指针，分别指向链表的头部。然后让第⼀个链表的指针先⾛ k=1 步。 这样就相当于指针后⾯的两个链表等⻓了。

就可以开始⽐较，如果不相等，则两个指针都往后移动即可，知道节点为null。

  • 时间复杂度​：O(m+n)，需要遍历链表三次（两次计算长度，一次查找）

  • ​空间复杂度​：O(1)，只使用常数级别额外空间

但是上⾯的做法，如果公共节点在最后⼀个，假设⼀个链表⻓度为 n，⼀个为 m，那么计算个数就要全部遍历，需要 n+m 。两个链表都移动，到最后⼀个节点的时候才相等，也是 n+m，也就是 O(2*(n+m)) 。

双指针遍历法（最优）

有没有更加好⽤的做法呢？肯定有，我们来看：

两个链表分别是： 如果我在第⼀个链表后⾯拼接上第⼆个链表，第⼆个链表后⾯拼接上第⼀个链表，就会变成下⾯的样⼦： 发现了⼀个规律，也就是拼接之后的链表，是等⻓度的，第⼀个和第⼆个链表都从第⼀个开始⽐较，只要相等，就说明是第⼀个公共节点。也就是上⾯被圈起来的 6 节点。

原理如下：

  • 设链表1独有部分长度为a，链表2独有部分长度为b，公共部分长度为c

  • 指针p1路径：a + c + b

  • 指针p2路径：b + c + a

  • 两个指针路径长度相同，会在公共节点相遇

特殊情况处理：​​当两个链表没有公共节点时，两个指针会同时变为null，退出循环

  • 时间复杂度​：O(m+n)，每个指针遍历两个链表各一次

  • ​空间复杂度​：O(1)，只使用两个指针