02.07.链表相交

记录新手小白做题的过程。

题目：

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

在节点有两个链表 c1 开始相交：

保证 环不存在于整个链结构中。

请注意，函数返回结果后，链表必须 保持其原始结构 。

尝试：

想法：暴力解决方案，两个循环，一个记录A链数字，一个移动B链数字，如果两个结点相同，判断后面的数字是否相同，直到遇到结点。

class Solution { public:     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         ListNode *p1=headA;         ListNode *p2=headB;         int i=0,j=0;         for(;p1;i  ){             int count=p1->val;//记录p1结点的值             for(;p2;j  ){                 if(count==p2->val){//找到了相同数值的结点，判断后面的链表是否相等                         ListNode *cur=p2->next;                         ListNode *cur1=p1->next;                     while(cur){                         if(cur->val!=cur1->val){                             break;                         }                         cur=cur->next;                         cur1=cur1->next;                     }                     if(cur==nullptr&&cur1==nullptr)                         return p2->val;//如果，它们一直交到最后一个结点，找到了                 }                 p2=p2->next;             }             p1=p1->next;             p2=headB;//初始化p2         }         return null;     } };

编译错误显示在代码写出后。

1.cannot initialize return object of type 'ListNode *' with an lvalue of type 'int' return p2->val

不能初始化的类型是 'ListNode *' 左值类型为返回对象 'int' 返回 p2->val

大概意思是我需要返回结点，但我的返回已经成为Int整型

2.use of undeclared identifier 'null' return null;使用未声明的标识符"null"返回空

这个返回null看题解里写的。正确的应该是返回nullptr

改正后提交，对了44个，错了一个。

我不太明白我在哪个方向上犯了错误。如果这是错误的，其他的不应该是正确的。我怎么能跳过1 呢

看看别人的代码。

大神在评论区的做法：

点击链接

class Solution { public:     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         ListNode *A = headA, *B = headB;         while (A != B) {             A = A != B) {             A = A != nullptr ? A->next : headB;//遍历A，A是否等于空。为空继续遍历B，不为空则继续遍历             B = B != nullptr ? B->next : headA;//遍历B，类似上一行         }         return A;     } };

点击链接

class Solution { public:     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         ListNode* curA = headA;         ListNode* curB = headB;         int lenA = 0, lenB = 0;         while (curA != NULL) { // 求链表A的长度             lenA  ;             curA = curA->next;         }         while (curB != NULL) { // 求链表B的长度             lenB  ;             curB = curB->next;         }         curA = headA;         curB = headB;         // 让curA是最长链表的头，lenA为其长度         if (lenB > lenA) {             swap (lenA, lenB);             swap (curA, curB);         }         // 求长度差         int gap = lenA - lenB;         // 让curA和curB在同一起点(末尾对齐)         while (gap--) {             curA = curA->next;         }         // 遍历curA 和 curB，遇到同样的，直接返回         while (curA != NULL) {             if (curA == curB) {                 return curA;             }             curA = curA->next;             curB = curB->next;         }         return NULL;     } };