【题目】
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.
【分析】
如果两个没有环的链表相交于某个节点,那么在这个节点之后的所有节点都是两个链表所共有的。
(1)遍历链表A,记录其长度len1,遍历链表B,记录其长度len2。
(2)按尾部对齐,如果两个链表的长度不相同,让长度更长的那个链表从头节点先遍历abs(len1-en2),这样两个链表指针指向对齐的位置。
(3)然后两个链表齐头并进,当它们相等时,就是交集的节点。
时间复杂度O(n+m),空间复杂度O(1)
【代码】
/*------------------------------------
* 日期:2015-01-31
* 作者:SJF0115
* 题目: 160.Intersection of Two Linked Lists
* 网址:https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len1 = 0,len2 = 0;
ListNode *pA,*pB;
pA = headA;
// 统计第一个链表节点数
while(pA){
++len1;
pA = pA->next;
}//while
pB = headB;
// 统计第一个链表节点数
while(pB){
++len2;
pB = pB->next;
}//while
pA = headA;
pB = headB;
// 长度相等且只一个节点一样
if(len1 == len2 && pA == pB){
return pA;
}//if
// pA指向长链表 pB指向短链表
if(len1 < len2){
pA = headB;
pB = headA;
}//if
// pA,Pb指向相同大小位置的节点上
int as = abs(len1- len2);
for(int i = 0;i < as;++i){
pA = pA->next;
}//while
// 比较是不是相交点
while(pA){
if(pA == pB){
return pA;
}//if
pA = pA->next;
pB = pB->next;
}//while
return nullptr;
}
};
【分析二】
双指针解法 ,时间复杂度O(n+m),空间复杂度O(1):
维护两个指针pA和pB,初始分别指向A和B。然后让它们分别遍历整个链表,每步一个节点。
当pA到达链表末尾时,让它指向B的头节点;类似的当pB到达链表末尾时,重新指向A的头节点。
如果pA在某一点与pB相遇,则pA或pB就是交点。
所以最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。
【代码二】
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
// 有空链表肯定无交点
if(pA == nullptr || pB == nullptr){
return nullptr;
}//if
while(pA && pB){
// 交点
if(pA == pB){
return pA;
}//if
if(pA->next && pB->next){
pA = pA->next;
pB = pB->next;
}
// 到达pA末尾,pB未到达
else if(!pA->next && pB->next){
pA = headB;
pB = pB->next;
}
// 到达pB末尾,pA未到达
else if(pA->next && !pB->next){
pA = pA->next;
pB = headA;
}
// 同时到达pA,pB末尾
else{
return nullptr;
}
}//while
}
};
【分析三】
双指针解法 ,时间复杂度O(n+m),空间复杂度O(1):
维护两个指针pA和pB,初始分别指向A和B。然后让它们分别遍历整个链表,每步一个节点。
当pA到达链表末尾时,让它指向B的头节点;类似的当pB到达链表末尾时,重新指向A的头节点。
如果pA在某一点与pB相遇,则pA或pB就是交点。
所以最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。
【代码三】
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
// 有空链表肯定无交点
if(pA == nullptr || pB == nullptr){
return nullptr;
}//if
while(pA != nullptr && pB != nullptr && pA != pB){
pA = pA->next;
pB = pB->next;
// 交点 或者 null
if(pA == pB){
return pA;
}
// 到达pA末尾
if(pA == nullptr){
pA = headB;
}//if
// 到达pB末尾
if(pB == nullptr){
pB = headA;
}//if
}//while
return pA;
}
};
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起...160.Intersection of Two Linke
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
刷leetcode总结.md
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
My Solutions to Leetcode problems. All solutions support C
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi