leetcode——相交链表_leetcode两链表相交

在找两个链表相交的节点，首先要考虑的是这两个链表是否相交，若是不相交则返回空指针，如果相交，则找到相应的节点返回。对于这种节点问题，还需要考虑极端情况，加入其中一个链表是空指针怎么办，那此时就更不可能有相交的节点了，仍是返回空指针如图：

（一）类比于顺序表的问题，对待这个问题我们最简单粗暴的方法就是将两个链表中的节点依次比较，这种方法思路虽然简单，但是执行起来比较复杂，假设A链表有M个节点，B链表有N个节点，这种方法下来的话，比较次数过多，时间复杂度是0（M*N）
（二）
那么如何判断两个链表是否有相交节点呢

根据图片我们来看，按着链表A的顺序依次为a1->a2->c1->c2->c3，顺着链表B为b1->b2->b3->c1->c2->c3，依照两个链表的顺序我们可以发现两个链表在到达相交的节点后的节点是完全相同的，因此我们可以判断两个链表的最后一个节点是否相同来判断两个链表是否有节点
要如何找到这个节点呢，可以定义两个指针，依次向后访问，若是相同则是相交的节点，但是如果在节点之前A，B的节点数不一样怎么办呢

我们可以再找结尾的结点的时候就统计出两个链表的节点个数，让节点数多的先向后走两个节点个数之差个节点，这时相当于之后的长度是相同的，因此直接以此判断即可

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * curA=headA;
    struct ListNode * curB=headB;
    if(headA==NULL||headB==NULL)//判断两个链表中是否有空指针
    {
        return NULL;
    }
    int countA=0;
    int countB=0;
    int count=0;
    while(curA->next)
    {
        curA=curA->next;//找A链表的最后一个节点
        countA++;//统计链表中节点的个数
    }
    while(curB->next)
    {
        curB=curB->next;
        countB++;
    }
    if(curA!=curB)
    {
        return NULL;//判断A和B是否有相交节点，如果没有，则返回NULL
    }
    else
    {
        curA=headA;curB=headB;
        if(countA>countB)
        {
            count=countA-countB;
            while(count--)
            {
             curA=curA->next;
            }
        }
        else
        {
          count=countB-countA;
          while(count--)
          {
              curB=curB->next;
          }
        }
        while(curA!=curB)
        {
            curA=curA->next;
            curB=curB->next;
        }//两个链表依次向后，寻找相交的节点
        struct ListNode * point=curA;
        return point;

    }

}
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
46
47
48
49
50
51
52
53
54