找链表的交点

题目首先规定了两链表不为空，所以写代码的时候就不需要考虑链表为空的情况

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   
    struct ListNode *cur1=headA;
    struct ListNode *cur2=headB;
    int long1=1;
    int long2=1;
    //找到两链表的尾节点，并算数各自的长度
    while(cur1->next)
    {
        cur1=cur1->next;
        long1++;
    }
     while(cur2->next)
    {
        cur2=cur2->next;
        long2++;
    }
    //如果尾节点不相等，就不会相交
    if(cur1!=cur2)
    {
        return NULL;
    }
    //abs函数求出绝对值（两节点的长度差）
    int k=abs(long1-long2);
//假设法找到巧妙运用到长节点
   struct ListNode *longList=headA;
   struct ListNode *shortList=headB;
   if(long1<long2)
   {
         longList=headB;
         shortList=headA;
   }
   //长的先走k步
   while(k--)
   {
       longList=longList->next;
   }
   //一起走
   while(longList!=shortList)
   {
       longList=longList->next;
       shortList=shortList->next;
   }
   //返回交点longList或shortList
   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
46
47

值得注意的是这里用到了求两整形绝对值的函数asb

还有在判断那个链表长的时候并没有直接明确的去找，因为计算机是已经知道long1和long2的长度的，所以计算机是知道那个长的，所以我们只要假设一下