C++ 刷题笔记：链表相交问题详解

C++ 刷题笔记：链表相交问题详解

引用

CSDN

1.

https://m.blog.csdn.net/pinkpig232333/article/details/140637694

本文将带你解决一个经典的链表问题：寻找两个单链表相交的起始节点。通过详细解析题目要求、解题思路，并提供完整的C++代码实现，帮助你掌握链表操作和指针用法。

题目描述

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

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

题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at ‘8’

解释：相交节点的值为 8（注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。

在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解题思路

注意，先审题：是相交的节点而不是相同的值！！也就是说，当A和B的指针指向同一个地方（节点）的时候，其就是链表相交的起始节点。

解法是：

• 定义指针 curA = headA，curB = headB
• 先求出两个链表其各自的长度
• 求出长度差
• 然后让 curA 移动到，和 curB 末尾对齐的位置
• 此时我们就可以比较 curA 和 curB 是否相同，如果不相同，同时向后移动 curA 和 curB，如果遇到 curA == curB，则找到交点
• 否则循环退出返回空指针

代码实现

#include<iostream>
#include<vector>
using namespace std;

/*链表相交*/
struct LinkedNode{
    int val;
    LinkedNode *next;
    LinkedNode (int x):val(x),next(nullptr){}
    LinkedNode(int x,LinkedNode *next):val(x),next(next){}
};

class Solution{
public:
    LinkedNode *getIntersectionNode(LinkedNode *headA,LinkedNode *headB)
    {
        LinkedNode *curA = headA;
        LinkedNode *curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != nullptr)//求A链表的长度
        {
            lenA ++;
            curA = curA->next;
        }
        while(curB != nullptr)//求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 != nullptr)
        {
            if(curA == curB)
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
    void printflist(LinkedNode *head)//打印链表
    {
        LinkedNode *cur = head;
        while(cur != nullptr)
        {
            cout << cur->val <<" ";
            cur = cur->next;
        }
        cout << endl;
    }
};

int main(void)
{
    Solution s;
    //定义了和示例相同的两个链表
    LinkedNode *tail = new LinkedNode(5,nullptr);
    LinkedNode *tail1 = new LinkedNode(4,tail);
    LinkedNode *tail2 = new LinkedNode(8,tail1);
    LinkedNode *A3 = new LinkedNode(1,tail2);
    LinkedNode *A2 = new LinkedNode(0,A3);
    LinkedNode *A = new LinkedNode(5,A2);
    LinkedNode *b1 = new LinkedNode(1,tail2);
    LinkedNode *b = new LinkedNode(4,b1);
    //打印链表
    cout << "A: ";
    s.printflist(A);
    cout << "B: ";
    s.printflist(b);
    //找出两个单链表相交的起始节点并打印
    LinkedNode *Node = s.getIntersectionNode(A,b1);
    cout << "interdected at " << Node->val << endl;
    return 0;
}

总结

这是一道链表操作的基础题目，主要考察对链表指针的使用。通过本题，可以巩固链表的基本操作，如遍历、求长度等，同时加深对指针的理解。