LeetCode 160 相交链表 | 极客日志

C++算法

LeetCode 160 相交链表

讲解 LeetCode 第 160 题相交链表的解法。题目要求找出两个单链表相交的起始节点，若不相交则返回空指针。文章提供了两种思路：暴力解法通过双重循环比较节点地址，时间复杂度为 O(n^2)；优化方案先计算两链表长度差，让长链表指针先行，再同步移动寻找交点，时间复杂度 O(m+n)，空间复杂度 O(1)。代码使用 C++ 实现，包含基础实现与逻辑优化版本。

深海蔚蓝发布于 2026/3/30更新于 2026/4/131 浏览

LeetCode 160 相交链表

题目描述

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

图片描述

图片描述

图片描述

题目与思路分析

目标分析：

给定两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 nullptr。
提高要求：时间复杂度为 O(m + n)，空间复杂度为 O(1)，其中 m 和 n 分别为两个链表的长度。

思路一：暴力解法

思路：两层循环遍历链表 A 和链表 B，将链表 A 中的每个结点的地址都和链表 B 中的每个结点的地址进行比较，如果地址相等，则相交。

操作：

ListNode* curNode1 = headA, *curNode2 = headB：curNode1和curNode2分别用于迭代遍历两个链表。
链表 A 中的每个节点需要和链表 B 中的每个结点进行比较。
- curNode1 == curNode2时：代表是相交的结点，返回当前结点即可。
- else：内层循环中，curNode2移向下一个节点。
内层循环结束一轮后：
- 链表 A 的 curNode1向后移动：curNode1 = curNode1->next。
- 链表 B 的迭代结点回到链表 B 的头结点，准备进行下一轮遍历：curNode2 = headB;。
循环内没有 return 时，代表没有相交。循环结束后 return nullptr;。
时间复杂度 O(n^2)，空间复杂度。

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

O(1)

while(curNode1){
    while(curNode2){
        if(curNode1 == curNode2) return curNode1;
        else curNode2 = curNode2->next;
    }
    curNode1 = curNode1->next;
    curNode2 = headB;
}

private: 
size_t getLength(ListNode* list){ 
    ListNode* curNode = list; 
    size_t length =0;
    while(curNode){
        ++length; 
        curNode = curNode->next;
    }
    return length;
}

// 暴力解法 O(n^2)
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *curNode2 = headB;
        while(curNode1){
            while(curNode2){
                if(curNode1 == curNode2) return curNode1;
                else curNode2 = curNode2->next;
            }
            curNode1 = curNode1->next;
            curNode2 = headB;
        }
        return nullptr;
    }
};

// 时间复杂度为 O(m + n) 的解法
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *curNode2 = headB;
        // 分别求两个链表的长度
        size_t lengthA = getLength(headA);
        size_t lengthB = getLength(headB);
        // 长的链表先走差距步
        if(lengthA > lengthB){
            size_t gap = lengthA - lengthB;
            while(gap--) curNode1 = curNode1->next;
        } else {
            size_t gap = lengthB - lengthA;
            while(gap--) curNode2 = curNode2->next;
        }
        // 两个链表再同时走，第一个相同的地址就是交点
        while(curNode1){
            if(curNode1 == curNode2) return curNode1;
            else{
                curNode1 = curNode1->next;
                curNode2 = curNode2->next;
            }
        }
        return nullptr;
    }
private:
    size_t getLength(ListNode* list){
        ListNode* curNode = list;
        size_t length =0;
        while(curNode){
            ++length;
            curNode = curNode->next;
        }
        return length;
    }
};

// 优化找长链表的逻辑 时间复杂度为 O(m + n) 的解法
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *curNode2 = headB;
        // 分别求两个链表的长度
        size_t lengthA = getLength(headA);
        size_t lengthB = getLength(headB);
        // 长的链表先走差距步
        // 优化找长的链表的逻辑，假设 A 比 B 长，再加一个修正假设的逻辑
        ListNode* longList = headA, *shortList = headB;
        size_t gap = lengthA - lengthB;
        if(lengthA < lengthB){
            longList = headB;
            shortList = headA;
            gap = lengthB - lengthA;
        }
        // 长链表先走差距步
        while(gap--) longList = longList->next;
        // 两个链表再同时走，第一个相同的地址就是交点
        while(longList){
            if(longList == shortList) return longList;
            else{
                longList = longList->next;
                shortList = shortList->next;
            }
        }
        return nullptr;
    }
private:
    size_t getLength(ListNode* list){
        ListNode* curNode = list;
        size_t length =0;
        while(curNode){
            ++length;
            curNode = curNode->next;
        }
        return length;
    }
};