「题解」相交链表

🍉题目

题目链接

🍉解析

“提示”部分有提示链表数不为零，所以讨论链表为空的情况。
最简单粗暴的思路就是：遍历链表，先使用循环遍历A链表，然后嵌套循环遍历B，比对A、B是否存在地址相同的节点，若有，则第一个这样的节点就是相交的起点。
这里的思路就是比对地址，我们不能比较节点值是否相等，毕竟不同节点的值可以相等
但是这样的时间复杂度为O（N^2），显然不是最优解法。下面来看比较好的解法。
知道大思路是比较地址相不相等之后，还有一个问题：两个链表的长度不一样。这个问题倒是不难解决，我们直接让长的链表先走，它比短的链表多几个节点，就先走几个节点，既然如此，那先来获取链表长度吧。

int len1 = 0,len2 = 0;
    ListNode* cur1 = headA,*cur2 = headB;
    
    //得到两链表长度
    while(cur1) {
        cur1 = cur1->next;
        len1++;
    }
    while(cur2) {
        cur2 = cur2->next;
        len2++;
    }
    int gap = abs(len1 - len2); //求出相差几个节点
1
2
3
4
5
6
7
8
9
10
11
12
13

这里用绝对值函数abs，就不用分类讨论len1、len2谁比较长了
然后又有一个问题，我不知道谁比较长啊，又要写条件语句分类讨论了……
其实大可不必，这里使用假设法就非常省事儿了，怎么个假设法？一开始假设A是长链表，B是短链表，写个 if ：如果 len1 真比 len2 长，就往下走；如果 len1 比 len2 短，那就A和B交换。

ListNode* longlist = headA; //先假设a是较长的链表
    ListNode* shortlist = headB;
    if(len1 < len2) {
        longlist = headB;
        shortlist = headA;
    }
    while(gap--) {
        longlist = longlist->next;
    }
1
2
3
4
5
6
7
8
9

那现在A和B要走的节点数就一样了，接下来边走边比较咯。
整道题代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int len1 = 0,len2 = 0;
    ListNode* cur1 = headA,*cur2 = headB;
    
    //得到两链表长度
    while(cur1) {
        cur1 = cur1->next;
        len1++;
    }
    while(cur2) {
        cur2 = cur2->next;
        len2++;
    }
    int gap = abs(len1 - len2); //求出相差几个节点
    ListNode* longlist = headA; //先假设a是较长的链表
    ListNode* shortlist = headB;
    if(len1 < len2) {
        longlist = headB;
        shortlist = headA;
    }
    while(gap--) {
        longlist = longlist->next;
    }
    while(longlist) {
        if(longlist == shortlist) {
            return longlist;
        }
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return NULL;
}
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