力扣160：相交链表

力扣160：相交链表

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

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

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at ‘8’

示例 2：

输入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出： Intersected at ‘2’

输入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出： null

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

分析：

1. 解法1：暴力求解

分别遍历链表A和链表B，找到两个链表地址相同的位置即可，但是时间复杂度很高，O（n²）

2. 解法2：

• 分别找尾节点，并记录两个链表的长度
• 如果尾节点的地址不一样，则说明没有公共交点。注意：是比较地址，不是比较值
• 遍历两个链表，返回相同的节点即可：
  （1）计算两个链表长度的差值，让长的链表先遍历，当长度一致时，再两个链表一起遍历。定义两个指针，一个指向较长的哪一个链表longlist,一个指向较短的链表shortlist.两个链表的长度我们不知道哪一个长哪一个短，因此需要先去判断，让较长的链表先遍历。这里有一个比较简便方法：用A链表的长度-B链表的长度，并取绝对值，假设链表A的长度较长，使longlist指向A链表的头节点headA，shortlist指向B链表的头节点headB。但是，这只是假设，实际情况不知道是怎样的。所以用一个if语句，如果链表A的长度小于链表B的长度，那么规定longlist为链表B的头节点headB，shortlist为链表A的头节点headB。

（2）先让长的先遍历。

（3）两个链表同时遍历，如果longlist=shortlist，说明两个链表的当前节点地址相同，表明此节点为交点，则停止遍历，最后返回这个节点即可。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*curA=headA,*curB=headB;
    int lenA=1,lenB=1;

    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }

    if(curA!=curB)
    {
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode*longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45