【LeetCode_160】相交链表

刷爆LeetCode系列

• LeetCode第160题：
• github地址
• 前言
• 题目描述
• 题目与思路分析
  • 思路一：暴力解法
  • 思路二：快慢指针
• 代码实现
  • 思路一：暴力解法
  • 思路二：快慢指针
• 算法代码优化

LeetCode第160题：

github地址

有梦想的电信狗

前言

本文用C++实现LeetCode第160题

题目描述

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

题目与思路分析

目标分析：

1. 给定两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。
2. 如果两个链表不存在相交节点，返回 nullptr
3. 提高要求：时间复杂度为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)，空间复杂度O(1)

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

思路二：快慢指针

思路：快慢指针解法

1. 先分别求两个链表的长度
2. 长的链表的curNode指针先向后移动两个链表长度的差距步
3. 两个迭代指针再同时移动，第一个地址相同的结点就是交点

操作：

• 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;}};

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀