LintCode-380.两个链表的交叉
2024-08-27 21:57:37
两个链表的交叉
请写一个程序,找到两个单链表最开始的交叉节点。
注意事项
- 如果两个链表没有交叉,返回null。
- 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
样例
下列两个链表:
在节点 c1 开始交叉。挑战
需满足 O(n) 时间复杂度,且仅用 O(1) 内存。
标签
链表
code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// write your code here
stack<ListNode *> stackA, stackB;
ListNode * result=NULL,*pA=headA,*pB=headB;
if(headA==NULL || headB==NULL)
return result;
while(pA != NULL) {
stackA.push(pA);
pA = pA->next;
}
while(pB != NULL) {
stackB.push(pB);
pB = pB->next;
}
while(!stackA.empty() && !stackB.empty()) {
if(stackA.top() == stackB.top()) {
result = stackA.top();
stackA.pop();
stackB.pop();
}
else {
break;
}
}
return result;
}
};
最新文章
- Github装(zao)逼(jia)指(da)南(fa)
- C# 反转字符串
- minicom的安装与配置
- 在VMware Workstation上安装Kali Linux
- van Emda Boas
- 利用 Postfix 抵擋垃圾信
- SQL Server 2008 序列号
- oracle11g 创建用户并授权
- 17.2.2 Replication Relay and Status Logs 复制Relay 和状态日志;
- 【Java Web】使用URLRewrite实现网站伪静态
- 【剑指Offer学习】【面试题17 ::合并两个排序的链表】
- 腾讯云数据库团队:浅谈如何对MySQL内核进行深度优化
- ASP.NET Core实现强类型Configuration读取配置数据
- Android按下home键后重新打开app进入主activity的问题
- JS基础:常用API
- python3 re模块正则匹配字符串中的时间信息
- 三丶JavaScript 的基础学习(一)
- opencv 常用头文件介绍
- 2.23日刷数论题后总结(题目整理自SCUT
- Anaconda使用总结
热门文章
- 【淘宝客】批量提取QQ号
- PyPI - Datetime
- SaltStack error: No module named &#39;salt&#39;
- python教程(二)&#183;第一个python程序
- Multiclonal Invasion in Breast Tumors Identified by Topographic Single Cell Sequencing
- 利用cross-entropy cost代替quadratic cost来获得更好的收敛
- 如何配置 SpaceVim
- 快速创建一个vue项目
- PHP实现识别带emoji表情的字符串
- 【原创】Odoo开发文档学习之:构建接口扩展(Building Interface Extensions)(边Google翻译边学习)