【LeetCode_160】相交链表
刷爆LeetCode系列
LeetCode第160题：
github地址
前言
本文用C++实现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;
- 链表A的
- 循环内没有
return时，代表没有相交。循环结束后return nullptr; - 时间复杂度
O(n^2)，空间复杂度O(1)
while(curNode1){while(curNode2){if(curNode1 == curNode2)return curNode1;else curNode2 = curNode2->next;} curNode1 = curNode1->next; curNode2 = headB;}思路二：快慢指针
思路：快慢指针解法
- 先分别求两个链表的长度
- 长的链表的
curNode指针先向后移动两个链表长度的差距步 - 两个迭代指针再同时移动，第一个地址相同的结点就是交点
操作：
ListNode* curNode1 = headA, *curNode2 = headB：curNode1和curNode2分别用于迭代遍历两个链表- 求链表长度的子函数
- 分别求两个链表的长度：
size_t lengthA = getLength(headA)，size_t lengthB = getLength(headB);
- 比较两个链表的长度，长的链表的
curNode指针先移动差距步 - 再让两个
curNode指针同时移动，第一个相同的地址就是交点 - 时间复杂度
O(m + n)，空间复杂度O(1)
private: size_t getLength(ListNode* list){ ListNode* curNode = list; size_t length =0;while(curNode){++length; curNode = curNode->next;}return length;}
代码实现
思路一：暴力解法
- 暴力解法：时间复杂度
O(n^2)，空间复杂度O(1)
// 暴力解法 O(n^2)classSolution{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;}returnnullptr;}};思路二：快慢指针
- 快慢指针解法：时间复杂度
O(m + n)，空间复杂度O(1)，其中m和n分别为两个链表的长度
// 时间复杂度为O(m + n)的解法classSolution{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;}}returnnullptr;}private: size_t getLength(ListNode* list){ ListNode* curNode = list; size_t length =0;while(curNode){++length; curNode = curNode->next;}return length;}};算法代码优化
- 思路二代码优化：优化比较链表长度的逻辑，减少逻辑重复的代码
// 优化找长链表的逻辑 时间复杂度为O(m + n)的解法classSolution{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;}}returnnullptr;}private: size_t getLength(ListNode* list){ ListNode* curNode = list; size_t length =0;while(curNode){++length; curNode = curNode->next;}return length;}};以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步
分享到此结束啦你的每一次互动，都是对作者最大的鼓励！
一键三连，好运连连！征程尚未结束，让我们在广阔的世界里继续前行！🚀
