02.07. 链表相交

 1 //暴力法
 2     ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
 3         if (headA == nullptr || headB == nullptr) return nullptr;
 4         ListNode* p, * q;
 5         p = headA;
 6         q = headB;
 7         while (p != nullptr)
 8         {
 9             q = headB;
10             while (q != nullptr)
11             {
12                 if (p == q)
13                     return p;
14                 q = q->next;
15             }
16             p = p->next;
17         }
18         if (p == nullptr || q == nullptr) return nullptr;
19         else return p;
20     };
21     //差值法
22     ListNode* getIntersectionNode1(ListNode* headA, ListNode* headB) {
23         if (headA == nullptr || headB == nullptr) return nullptr;
24         ListNode* curA = headA;
25         ListNode* curB = headB;
26         int lenA = 0, lenB = 0;
27         while (curA != NULL) { // 求链表A的长度
28             lenA++;
29             curA = curA->next;
30         }
31         while (curB != NULL) { // 求链表B的长度
32             lenB++;
33             curB = curB->next;
34         }
35         if (lenB > lenA)
36         {
37             swap(lenB, lenA);
38             swap(curA, curB);
39         }
40         int gap = lenA - lenB;
41         while (gap--)
42         {
43             curA = curA->next;
44         }
45         while (curA != NULL) {
46             if (curA == curB) {
47                 return curA;
48             }
49             curA = curA->next;
50             curB = curB->next;
51         }
52         return NULL;
53     };