Intersection of Two Linked Lists (求两个单链表的相交结点)
2024-10-09 01:25:02
题目描述:
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.
solution:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL)
return NULL;
int lenA = ;
int lenB = ;
ListNode *pA = headA;
while (pA != NULL)
{
++lenA;
pA = pA->next;
}
ListNode *pB = headB;
while (pB != NULL)
{
++lenB;
pB = pB->next;
} if (pA != pB)
return NULL; pA = headA;
pB = headB; if (lenA > lenB)
{
int k = lenA - lenB;
while (k--)
{
pA = pA->next;
}
}
else
{
int k = lenB - lenA;
while (k--)
{
pB = pB->next;
}
} while (pA != pB)
{
pA = pA->next;
pB = pB->next;
}
return pA;
}
上述解法来自《剑指offer》,还有一种基于Hashset的方法。
solution:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL)
return NULL;
unordered_set<ListNode*> st;
while (headA != NULL)
{
st.insert(headA);
headA = headA->next;
} while (headB != NULL)
{
if (st.find(headB) != st.end())
return headB;
headB = headB->next;
}
return NULL;
}
最新文章
- 深入学习jQuery选择器系列第七篇——表单选择器
- Mysql优化系列(2)--通用化操作梳理
- SpringMVC原理解析-Servlet容器启动时初始化SpringMVC应用的原理
- C#装箱和拆箱
- 恶趣味小游戏 I&#39;m hungry
- HDU 4123 (2011 Asia FZU contest)(树形DP + 维护最长子序列)(bfs + 尺取法)
- linux命令行与shell脚本编程大全---更多bash shell命令
- 分享7款非常实用的jQuery/CSS3插件演示和源码
- Java基础--重写(Overriding,覆盖)-重载(Overloading)
- HTML中的IE条件注释
- HDU-4511 小明系列故事——女友的考验 floyd变种-标号递增最短路
- salt 批量部署与配置
- 第二篇、微信程序尺寸rpx
- [Redux] Extracting Presentational Components -- Todo, TodoList
- NOIP2005-普及组复赛-第三题-采药
- 给Lisp程序员的Python简介
- confluence6.x安装
- mysql 执行语句
- spring MVC 如何接收前台传入的JSON对象数组并处理
- Integer Array Ladder questions
热门文章
- 数据结构和算法(Golang实现)(25)排序算法-快速排序
- Crowd 批量添加用户(Postman 数据驱动)
- 在Python中该如何实现Java的重写与重载
- B - Raising Modulo Numbers
- Shellshock远程命令注入(CVE-2014-6271)漏洞复现
- 两种异常(CPU异常、用户模拟异常)的收集
- go的 三个点 ...
- 微信小程序填坑---小程序支付
- What does __GNUC__ mean?
- 获取磁盘的 总容量,空余容量,已用容量 【windows】