C++实现LeetCode(160.求两个链表的交点)
[LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
我还以为以后在不能免费做OJ的题了呢,想不到 OJ 又放出了不需要买书就能做的题,业界良心啊,哈哈^_^。这道求两个链表的交点题要求执行时间为 O(n),则不能利用类似冒泡法原理去暴力查找相同点,事实证明如果链表很长的话,那样的方法效率很低。我也想到会不会是像之前删除重复元素的题一样需要用两个指针来遍历,可是想了好久也没想出来怎么弄。无奈上网搜大神们的解法,发觉其实解法很简单,因为如果两个链长度相同的话,那么对应的一个个比下去就能找到,所以只需要把长链表变短即可。具体算法为:分别遍历两个链表,得到分别对应的长度。然后求长度的差值,把较长的那个链表向后移动这个差值的个数,然后一一比较即可。代码如下:
C++ 解法一:
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return NULL; int lenA = getLength(headA), lenB = getLength(headB); if (lenA < lenB) { for (int i = 0; i < lenB - lenA; ++i) headB = headB->next; } else { for (int i = 0; i < lenA - lenB; ++i) headA = headA->next; } while (headA && headB && headA != headB) { headA = headA->next; headB = headB->next; } return (headA && headB) ? headA : NULL; } int getLength(ListNode* head) { int cnt = 0; while (head) { ++cnt; head = head->next; } return cnt; } };
Java 解法一:
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; int lenA = getLength(headA), lenB = getLength(headB); if (lenA > lenB) { for (int i = 0; i < lenA - lenB; ++i) headA = headA.next; } else { for (int i = 0; i < lenB - lenA; ++i) headB = headB.next; } while (headA != null && headB != null && headA != headB) { headA = headA.next; headB = headB.next; } return (headA != null && headB != null) ? headA : null; } public int getLength(ListNode head) { int cnt = 0; while (head != null) { ++cnt; head = head.next; } return cnt; } }
这道题还有一种特别巧妙的方法,虽然题目中强调了链表中不存在环,但是我们可以用环的思想来做,我们让两条链表分别从各自的开头开始往后遍历,当其中一条遍历到末尾时,我们跳到另一个条链表的开头继续遍历。两个指针最终会相等,而且只有两种情况,一种情况是在交点处相遇,另一种情况是在各自的末尾的空节点处相等。为什么一定会相等呢,因为两个指针走过的路程相同,是两个链表的长度之和,所以一定会相等。这个思路真的很巧妙,而且更重要的是代码写起来特别的简洁,参见代码如下:
C++ 解法二:
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return NULL; ListNode *a = headA, *b = headB; while (a != b) { a = a ? a->next : headB; b = b ? b->next : headA; } return a; } };
Java 解法二:
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode a = headA, b = headB; while (a != b) { a = (a != null) ? a.next : headB; b = (b != null) ? b.next : headA; } return a; } }
类似题目:
Minimum Index Sum of Two Lists
参考资料:
https://leetcode.com/problems/intersection-of-two-linked-lists/
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49792/Concise-JAVA-solution-O(1)-memory-O(n)-time
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
到此这篇关于C++实现LeetCode(160.求两个链表的交点)的文章就介绍到这了,更多相关C++实现求两个链表的交点内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25