剑指offer 36. 两个链表的第一个公共结点

36. 两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

法一：双指针法，复杂度O(2n)

两个指针同时遍历两个链表，每个指针遍历完当前链表继续遍历另一链表，当两个指针相等或者某个指针为空时退出循环

定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点

假定 p1 指向表 a , p2 指向表 b, 两个链表公共结点之后的长度肯定相等，因为是同一段链表。所以长度不等只能来自公共结点之前的部分。

两个链表的第一个公共结点之前的长度要么相等，要么不相等，如果相等，那么两个指针 p1 , p2 同时后移，肯定能同时找到公共结点；如果两个链表的长度不一样，那么比如 a 链表比 b 链表长 k 个结点，那么当 p2 到达 b 链表的表尾的时候，p1 肯定距离到达 a 链表表尾还差 k 个结点，随后 p2 开始从 a 链表的表头开始遍历。当 p1 链表到达表尾时后，p1 从 b 链表的表头开始遍历, 此时 p2 已经在 a 链表上走了 k 个结点，而 p1 在 b 链表上才刚起步，走了 0 个结点，而恰好 a 就比 b 长 k 个结点，所以 p1 和 p2 会同时到达公共结点。

链表1 在公共结点之前的结点个数为 a1, 公共结点之后的结点个数为 a2, 同理，链表2 在公共结点之前的结点个数为 b1, 公共结点之后的结点个数为 b2, 因为公共结点的之后的部分是同一条链表，所以a2 == b2, 所以上面的思路就是 a1 + b1 == b1 + a1

 1 public class Solution {
 2     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 3         if(pHead1 == null || pHead2 == null){
 4             return null;
 5         }
 6         ListNode p1 = pHead1;
 7         ListNode p2 = pHead2;
 8         while(p1 != p2 && (p1 != null && p2 != null)){
 9             p1 = p1.next;
10             p2 = p2.next;
11             if(p1 != p2){
12                 if(p1 == null) 
13                     p1 = pHead2;
14                 if(p2 == null)
15                     p2 = pHead1;
16             }
17         }
18        return p1;
19     }
20 }

你变成我，走过我走过的路。

我变成你，走过你走过的路。

然后我们便相遇了..

复杂度分析：

 1 public class Solution {
 2     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 3         
 4         // 两个指针同时遍历两个链表，每个指针遍历完当前链表继续遍历另一链表，当两个指针相等或者某个指针为空时退出循环
 5         ListNode p1 = headA, p2 = headB;
 6         while(p1 != p2){
 7             p1 = (p1 != null) ? p1.next : headB;
 8             p2 = (p2 != null) ? p2.next : headA;
 9         }
10         return p1;
11     }
12 }

leetcode运行时间为1ms, 空间为41.4MB

复杂度分析：

时间复杂度：最多把两个链表合起来遍历一遍，所以时间复杂度为O(M+N)

空间复杂度：O(1)

法二：双重循环法, 算法复杂度 O(n^2)

 1 public class Solution {
 2     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 3          // 双重循环遍历两个链表
 4         ListNode cur1 = pHead1;
 5         while(cur1 != null){
 6             ListNode cur2 = pHead2;
 7             while(cur2 != null){
 8                 if(cur2 == cur1)
 9                     return cur1;
10                 cur2 = cur2.next;
11             }
12             cur1 = cur1.next;
13         }
14         return cur1;
15     }
16 }

法三：

把其中一个链表存入HashSet中，遍历第二个链表，判断该结点是否存在于HashSet中，如果存在的话直接返回该结点