题目描述

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

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

图片

如图所示，则输出C1；具体见题目链接：题目链接

题目思路

这道题目我是不会的……我只能想到暴力破解，就是通过两层循环进行遍历，找到最开始的地址相同的节点，伪代码差不多是这样：：

1
2
3
4
5
6
7
8
9
10
11
tmpA = headA;
while(tmpA != NULL) {
  tmpB = headB;
  while (tmpB != NULL) {
    if (tmpA != tmpB) {
      return tmpA;
    }
    tmpB = tmpB->next;
  }
} 
return NULL;

​ 但是实际上是不行的，时间复杂度过不去，也不像是个算法，看了评论区一个大佬的讲解，这个思路是真厉害，讲的也很好。主要可以抽象成下面的数学语言：

  1. 假定链表A长度为m+a，链表B长度为n+a。为什么有一个公共的a呢？因为如果A，B有公共部分，那么其从公共节点出发，后面的部分肯定是一样的，节点数值和节表长度都一样
  2. 分别将从A，B开始遍历，那么经过Len(A)后到达A的末端，同样经过Len(B)后到达B的末端，然后执行：
  • 对于A，继续遍历B；对于B，紧跟着遍历A；
  • 那么A经过m+a+n后，刚好到达B链表上的公共节点的起始节点；B经过n+a+m后，刚好到达A链表上的公共节点的起始节点。此时两个遍历是同步的，正好位于公共节点上。

​ 伪代码如下：

1
2
3
4
5
6
7
8
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *tmpA = headA, *tmpB = headB;
        while (tmpA != tmpB) {
            tmpA = tmpA->next ? tmpA : headB;
            tmpB = tmpB->next ? tmpB : headA;
        }
        return tmpA;
    }

​ 只能说算法这个玩意儿真的得天赋……这么简单的题我只能暴力hhhh