LeetCode 160. 相交链表 | 三种解法吃透核心逻辑（哈希表 + 双指针 + 长度对齐）

前言

相交链表是链表类面试的高频题（难度★★☆☆☆），核心考察对链表遍历、指针操作的理解。最初我用哈希表解决，后续又学习了官方双指针法，以及更易理解的「长度对齐法」，三种解法各有优劣，现将完整思路、避坑点和复杂度分析整理如下。

题目描述

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

注：相交的定义是「节点地址相同」，而非节点值相同。

解法一：哈希集合（直观易想，空间换时间）

核心思路

利用哈希集合存储其中一个链表的所有节点，再遍历另一个链表，第一个在集合中匹配到的节点就是相交节点；若遍历完未匹配，说明无交点。

实现代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> nodeSet; // 存储链表A的所有节点 while(headA != NULL){ nodeSet.insert(headA); headA = headA->next; } // 遍历链表B，查找相交节点 while(headB != NULL){ if(nodeSet.find(headB) != nodeSet.end()){ return headB; } headB = headB->next; } return NULL; } };

复杂度分析

m、n分别为两个链表的长度

时间复杂度：O(m+n)：遍历链表 A 耗时 O(m)，遍历链表 B 匹配耗时 O(n)；

空间复杂度：O(m)，需存储链表 A 的所有节点，空间开销较大。

解法二：官方双指针法（最优解）

核心思路

两个指针分别从headA、headB出发，遍历到链表末尾时跳转到另一个链表的头节点继续遍历。

• 若链表相交：两个指针会在相交节点处相遇（移动总距离均为 m+n）；
• 若链表不相交：两个指针最终都会指向NULL（仍满足 p==q，直接返回即可）。

实现代码（避坑版）

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; ListNode* p = headA; ListNode* q = headB; // 核心：仅判断p!=q（允许p/q为NULL） while(p != q){ // 指针到末尾则跳转到另一链表头，否则走next p = p == NULL ? headB : p->next; q = q == NULL ? headA : q->next; } // 最终p==q：要么是相交节点，要么都是NULL return p; } };

避坑要点

重做这道题时曾写出「超时代码」，核心错误：

// 错误代码核心问题 while (p != NULL && q != NULL && p != q) { // 多余的非空判断 p = p->next != NULL ? p->next : headB; // 指针永远到不了NULL q = q->next != NULL ? q->next : headA; }

• 循环条件加p!=NULL && q!=NULL：无交点时指针永远无法相等，陷入死循环；
• 指针移动逻辑错误：p->next!=NULL导致指针永远到不了链表末尾，无法跳转到另一链表，违背双指针核心逻辑。

复杂度分析

m、n分别为两个链表的长度

时间复杂度：O(m+n)，最坏情况遍历两个链表所有节点；

空间复杂度：O(1)，仅使用两个指针变量，常数级开销。

解法三：长度对齐法

核心思路

相交链表的「交点后长度」完全一致，因此先计算两个链表的长度差，让较长链表的指针先移动「长度差」步，使两个指针到交点的距离一致，再同步遍历，第一个相等的节点即为交点。

实现代码

// 辅助函数：获取链表长度 int GetLength(ListNode* head) { int len = 0; while(head != NULL) { len++; head = head->next; } return len; } ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { if (headA == NULL || headB == NULL) return NULL; int lenA = GetLength(headA); int lenB = GetLength(headB); ListNode* p = headA; ListNode* q = headB; // 较长链表的指针先移动长度差 while (lenA > lenB) { p = p->next; lenA--; } while (lenB > lenA) { q = q->next; lenB--; } // 同步遍历，找第一个相等的节点 while (p != NULL && q != NULL) { if (p == q) return p; p = p->next; q = q->next; } return NULL; }

复杂度分析

m、n分别为两个链表的长度

时间复杂度：O(m+n)，计算长度遍历两次链表，对齐后遍历一次最短链表；

空间复杂度：O(1)，仅使用长度变量和指针。

三种解法对比

核心总结

1. 相交链表的核心是「节点地址相等」，而非值相等；
2. 最优解是官方双指针法，需牢记「指针到末尾跳另一链表头 + 仅判断 p!=q」的核心逻辑；
3. 长度对齐法更适合面试口述，哈希表法则适合快速实现，可根据场景选择。