Intersection of Two Linked Lists——经典问题
2024-10-22 10:48:53
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.
开始想道用栈来做,先入栈,然后出栈比较直接就出结果了,但是题目说只能利用一个空间,所以栈的方法不行了。
看网上的答案,没想到这么简单,暴力解法,什么算法、数据结构都没用,题刷多了,脑袋都僵了,一直以为要用什么算法来做呢。。。。
思路:
查找两个链表的第一个公共节点,如果两个节点的尾节点相同,肯定存在公共节点
方法: 长的链表开始多走 (h1的数量 - h2的数量)步,然后和短链表同步往下走,遇到的第一个相同的节点就是最早的公共节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL||headB==NULL)
return NULL;
ListNode *flagA=headA;
ListNode *flagB=headB;
int countA=;
int countB=;
while(flagA->next!=NULL)
{
countA++;
flagA=flagA->next;
}
while(flagB->next!=NULL)
{
countB++;
flagB=flagB->next;
}
if(flagA!=flagB)
return NULL;
else
{
int diff=abs(countA- countB);
if(countA>=countB)
{
flagA=headA;
flagB=headB;
}
else
{
flagA=headB;
flagB=headA;
}
while(diff)
{
flagA=flagA->next;
diff--;
}
while(flagA!=flagB)
{
flagA=flagA->next;
flagB=flagB->next;
}
return flagA;
}
}
};
最新文章
- macbook 重装win7
- HTTP基础05--http首部
- 为什么html5用的jQuery Mobile在手机浏览器/微信中打开字体很小
- CentOS 防火墙打开和关闭端口(转载)
- *[hackerrank]Jim Beam
- pyqt下拉菜单和打开指定的内容(或者exe,doc,ppt,url等内容)
- HighChart学习-更新数据data Series与重绘
- 安卓推送——个推服务端api使用误区
- 开箱即用 - Grunt合并和压缩 js,css 文件
- jquery ui-----弹出窗口 dialog
- java 图片处理 base64编码和图片二进制编码相互转换
- <;%@taglib prefix=";c"; uri=";http://java.sun.com/jsp/jst1/core";%>;报错
- loadrunner java / JAVA_HOME / CLASSPATH / PATH
- 打通MySQL架构和业务的任督二脉
- excel中批量删除公式,保留数值
- 线程9--NSOperation
- 【转】 Android中selector的使用
- timedatectl — Control the system time and date
- 深入理解java虚拟机,内存管理部分
- 解决emacs配置tern报错`tern-reparse-on-idle&#39;:
热门文章
- 史上最全Linux提权后获取敏感信息方法
- 解决webstrom 输入法光标不跟随问题
- oracle数据库解锁
- caffe中的Accuracy+softmaxWithLoss
- [mysql]mysql弱密码字典检测
- bzoj 1122 [POI2008]账本BBB 模拟贪心,单调队列
- jq 正则
- HDU5875 Function
- iOS 时间转换
- SpringBoot Caused by: java.lang.NoClassDefFoundError: org/apache/tomcat/util/descriptor/tld/TldParser