网站设计鉴赏,广州营销型网站建设价格,上海建设部网站,讨论建设网站的心得文章目录 两个链表的第一个公共结点问题描述示例说明示例 1示例 2 方法及实现方法描述代码实现 复杂度分析示例运行过程示例 1示例 2 总结备注 两个链表的第一个公共结点
问题描述
给定两个无环的单向链表#xff0c;找到它们的第一个公共节点。如果没有公共节点#xff0c… 文章目录 两个链表的第一个公共结点问题描述示例说明示例 1示例 2 方法及实现方法描述代码实现 复杂度分析示例运行过程示例 1示例 2 总结备注 两个链表的第一个公共结点
问题描述
给定两个无环的单向链表找到它们的第一个公共节点。如果没有公共节点则返回空。
要求
空间复杂度 O ( 1 ) O(1) O(1)时间复杂度 O ( n ) O(n) O(n)数据范围 链表长度 n ≤ 1000 n \leq 1000 n≤1000
输入数据分为三个部分
第一个链表的非公共部分。第二个链表的非公共部分。两个链表的公共部分。
后台会根据输入组装成两个单链表传入FindFirstCommonNode函数返回第一个公共节点。 示例说明 示例 1
输入 {1,2,3}, {4,5}, {6,7}
链表结构 第一个链表1 - 2 - 3 - 6 - 7 第二个链表4 - 5 - 6 - 7
输出 {6,7}
说明 两个链表从节点值为 6 的位置开始公共返回节点值为 6 的节点。 示例 2
输入 {1}, {2,3}, {}
链表结构 第一个链表1 第二个链表2 - 3
输出 {}
说明 两个链表没有公共节点返回 null。 方法及实现
方法描述
采用双指针法
设置两个指针 first 和 second 分别指向两个链表的头节点。当 first 和 second 不相等时指针逐步向后移动 如果某个指针到达链表尾部则跳转到另一个链表的头部。如果两个指针在某节点相遇则该节点为第一个公共节点。如果两指针遍历结束仍未相遇则无公共节点返回 NULL。
代码实现
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2) {if (pHead1 NULL || pHead2 NULL) {return NULL; // 如果任何一个链表为空直接返回 NULL}struct ListNode* first pHead1; // 指针 first 初始指向链表1头部struct ListNode* second pHead2; // 指针 second 初始指向链表2头部// 当两个指针不相等时继续循环while (first ! second) {first (first ! NULL) ? first-next : pHead2; // 如果 first 到达末尾跳转到链表2头部second (second ! NULL) ? second-next : pHead1; // 如果 second 到达末尾跳转到链表1头部}return first; // 返回第一个公共节点或 NULL
}复杂度分析 时间复杂度 每个指针最多遍历两个链表的长度总时间复杂度为 O ( n m ) O(n m) O(nm)其中 n n n 和 m m m 分别是两个链表的长度。 空间复杂度 只使用了两个指针空间复杂度为 O ( 1 ) O(1) O(1)。 示例运行过程
示例 1
输入{1,2,3}, {4,5}, {6,7} 链表11 - 2 - 3 - 6 - 7 链表24 - 5 - 6 - 7
初始first 指向 1second 指向 4。第一次遍历first 和 second 分别遍历各自链表到达尾部后跳转到另一链表头部。第二次遍历first 和 second 在节点 6 相遇。输出{6,7}。 示例 2
输入{1}, {2,3}, {} 链表11 链表22 - 3
初始first 指向 1second 指向 2。第一次遍历first 遍历到尾部后跳转到链表2头部second 遍历到尾部后跳转到链表1头部。第二次遍历first 和 second 均到达尾部NULL。输出{}。 总结
双指针法通过交替遍历链表保证了时间复杂度 O ( n m ) O(n m) O(nm)且额外空间复杂度为 O ( 1 ) O(1) O(1)。代码简单高效能够准确找到第一个公共节点或判定无公共节点。
备注
最开始我写的代码是这样的
while (first!second) {if(first-nex!NULL)first first-next;else first pHead2;if(second-next!NULL)second second-next;else second pHead1;}结果发现有问题如果两个不相交的链表改成下面的才正确
while (first!second) {if(first-next!NULL)first first-next;else first pHead2;if(second-next!NULL)second second-next;else second pHead1;}思考了下原因原来是如果按照旧的代码 if(first-next!NULL)那么说明当前是队尾使用 first first-next;相当于第一个把第二个连起来了两个队列相互首位相连原本不 else first pHead2;
