题解 | 链表相交

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//     // 在这里补充代码
//    for(ListNode*pa=headA;pa!=NULL;pa=pa->next){//双循环暴力遍历
//     for(ListNode*pb=headB;pb!=NULL;pb=pb->next){
//         if(pa==pb){
//             return pa;
//         }
//     }
//    }
//    return NULL;

// }

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // 在这里补充代码
   ListNode*pa=headA;//双指针法  两个指针同步走 走完一个到另一个表继续走 
   ListNode*pb=headB;//         相交的时候步数一样  
   while(pa!=pb){
      if(pa!=NULL){
         pa=pa->next;
      }
      else if(pa==NULL){
        pa=headB;
      }
       if(pb!=NULL){
         pb=pb->next;
      }
      else if(pb==NULL){
        pb=headA;
      }
   }
   return pa;

}







































//你不需要修改主函数内的代码！
int main() {
    // 读入数据
    int lenA, lenB, commonLen;
    cin >> lenA >> lenB >> commonLen;
    
    // 构建链表
    vector<ListNode*> nodesA(lenA - commonLen);
    vector<ListNode*> nodesB(lenB - commonLen);
    vector<ListNode*> nodesCommon(commonLen);
    
    // 读入并创建链表A的独立部分
    for (int i = 0; i < lenA - commonLen; i++) {
        int val;
        cin >> val;
        nodesA[i] = new ListNode(val);
        if (i > 0) nodesA[i-1]->next = nodesA[i];
    }
    
    // 读入并创建链表B的独立部分
    for (int i = 0; i < lenB - commonLen; i++) {
        int val;
        cin >> val;
        nodesB[i] = new ListNode(val);
        if (i > 0) nodesB[i-1]->next = nodesB[i];
    }
    
    // 读入并创建公共部分
    for (int i = 0; i < commonLen; i++) {
        int val;
        cin >> val;
        nodesCommon[i] = new ListNode(val);
        if (i > 0) nodesCommon[i-1]->next = nodesCommon[i];
    }
    
    // 连接链表
    ListNode* headA = nullptr;
    ListNode* headB = nullptr;
    
    if (lenA - commonLen > 0) {
        headA = nodesA[0];
        if (commonLen > 0) nodesA.back()->next = nodesCommon[0];
    } else if (commonLen > 0) {
        headA = nodesCommon[0];
    }
    
    if (lenB - commonLen > 0) {
        headB = nodesB[0];
        if (commonLen > 0) nodesB.back()->next = nodesCommon[0];
    } else if (commonLen > 0) {
        headB = nodesCommon[0];
    }
    
    // 调用函数获取结果
    ListNode* result = getIntersectionNode(headA, headB);
    
    // 输出结果
    if (result == nullptr) {
        cout << "null" << endl;
    } else {
        cout << result->val << endl;
    }
    
    // 清理内存
    for (auto node : nodesA) delete node;
    for (auto node : nodesB) delete node;
    for (auto node : nodesCommon) delete node;
    
    return 0;
}