LeetCode——160 Intersection of Two Linked Lists
2024-09-08 13:29:34
题目
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
代码
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = getLen(headA), lenB = getLen(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&&headB&&headA!=headB){
headA = headA->next;
headB = headB->next;
}
return (headA==headB) ? headA : NULL;
}
private:
int getLen(ListNode *list){
int cnt = 0;
ListNode *tmp = list;
while(tmp){
tmp = tmp->next;
++cnt;
}
return cnt;
}
};
思路
先计算出两个链表的长度,然后进行比较,将较长的链表缩短(即将头节点指针向后移),使得两个链表长度一致,然后让指针同时同步长迭代,当发现地址相同时则知道当前节点开始共用。
最新文章
- 汇编语言进阶和Makefile进阶---第二天
- 任务调度框架-Quartz.Net
- .Net语言 APP开发平台——Smobiler学习日志:用Gridview控件设计较复杂的表单
- 3D打印公司网站dedecms大气模板
- Xamarin.Forms——尺寸大小(五 Dealing with sizes)
- [MEAN Stack] First API -- 1. with Node.js, Express and MongoDB
- gridview 字段没有绑定由于column visible= false
- Fire Net
- NOIP2002 均分纸牌
- Direct3D 索引缓存
- Word常用实用知识3
- html之结构化标记
- sudo,visudo
- 如何在原生微信小程序中实现数据双向绑定
- 企业IT管理员IE11升级指南【14】—— IE11代理服务器配置
- MySQL数据库的sql语句的导出与导入
- 边学边做,简单的 GraphQL 实例
- GIT 私有仓库 github项目提交失败 master ->; master (non-fast-forward)
- netty源码理解(三) 从channel读取数据
- Scala中的柯里化
热门文章
- Python 操作sqlite数据库及保存查询numpy类型数据(二)
- man.conf - man的设定资料
- Ansible 管理Windows 受控端
- SOJ 一句话题解整理
- lambda匿名函数sorted排序函数filter过滤函数map映射函数
- nodejs第一天
- heroinfo_set.all 函数
- 【leetcode】1171. Remove Zero Sum Consecutive Nodes from Linked List
- 解决报错:The server time zone value &#39;&#214;&#208;&#185;&#250;&#177;&#234;&#215;&#188;&#202;&#177;&#188;&#228;&#39; is unrecognized
- 2014ACM-ICPC广州站题解(摘自闭幕式)