掌握链表——（八）LeetCode160.相交链表_gh中如何选择longlist

相交链表

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

思路一：暴力求解 --穷举
依次取A链表中的每个结点更B链表中的所有结点比较，如果有地址相同的结点，就是相交，第一个相同的就交点。
时间复杂为 O(N^2)。因为时间复杂度太高了，不用这个思路。

思路二：要求优化到O(N)
1.尾结点相同就是相交，否则不相交
2.求交点：长的链表先走（长度差）步，再同时走，第一个相同就是交点
1)

                 我们先解决第一个问题，判断链表是否相交，如果没有返回NULL。
                 
                  如果相交，则 ==他们的共同点是尾结点相同== 。

             
             
                                     上代码了
1
2
3
4
5
6
7

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode *tailA=headA;//计算链表长度用的
    struct ListNode *tailB=headB;
    //判断两链表是否有相交结点
    while(tailA->next)
    {
        tailA=tailA->next;
    }
    while(tailB->next)
    {
      tailB=tailB->next;
    }
    //不相交
    if(tailA!=tailB)
    {  
        return NULL;
    }
   // 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2）

                                    有交点，那么如何找到？
                       我们先在定义两个指针分别指向两个链表的头结点

                                          如图：
1
2
3
4

            shortList与longList同时走，每走一步就判断他们的地址是否相同，如果相同则找了
                        ，否则就继续找直到他们相遇
                        
                      那么如果B链表比A链表多一个数呢？会不会出问题？        
1
2
3
4

               通过上图，shortList与longList同时走，shortList 要先遇到交点c1,那么如何解决呢？
               我们可以先让B链表先走一步，也就说，那个链表长那个链表就先走，
               那么如何求出该先走多少步呢？
               很简单，求出（A链表长度-B 链表长度）的绝对值就是该走的步数。
1
2
3
4

假设longList已经走了先走的步数

     最后一步了，shortList与longList同时走，然后判断，……
1

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode *tailA=headA;//计算链表长度用的
    struct ListNode *tailB=headB;

 
    int lenA=0,lenB=0;// 两链表的长度
    
  // 1）
    //判断两链表是否有相交结点
    
    while(tailA->next)// 遍历链表A，并且求出链表长度
    {
        lenA++;
        tailA=tailA->next;
    }
    while(tailB->next)// 遍历链表B，并且求出链表长度
    {
        lenB++;
        tailB=tailB->next;
    }
    lenA++;lenB++;// 长度最后少了一个所以要自增1位
    
    //两链表的尾结点地址不相同则，不相交，两链表没有交点
    if(tailA!=tailB)
    {  
        return NULL;
    }
         //两个链表有交点
        //找出相交的起始结点
        //判断那个链表先走
  //2)  
          struct ListNode *shortList=headA;//假设最短链表为headA
          struct ListNode *longList=headB;// 假设最长链表为headB
          if(lenA>lenB)//如果假设是错误则进行调整
          {
              shortList=headB;
              longList=headA;
          }

          // 走差距
          int gap=abs(lenA-lenB);//abs函数求绝对值
          while(gap--)
          {
              longList=longList->next;
          }
     //3)//   两链表同时走，知道地址相同，地址相同代表，共同的交点找到了，起始交点也就找到了
          while(shortList!=longList)
          {
              shortList=shortList->next;
              longList=longList->next;
          }

          return shortList;// 返回起始交点地址
}
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
55