【Offer】[52] 【两个链表的第一个公共结点】
2024-09-01 05:57:39
题目描述
输入两个链表，找出它们的第一个公共结点。下图中6为公共结点：

思路分析
如果两个链表有公共节点，那么公共节点出现在两个链表的尾部。如果我们从两个链表的尾部开始往前比较，那么最后一个相同的节点就是我们要找的节点。
- 解决这个问题:分别把两个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。
- 首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。
测试用例
- 功能测试：输入的两个链表有公共节点:第一个公共节点在链表的中间，第一个公共节点在链表的末尾，第一个公共节点是链表的头节点;输入的两个链表没有公共节点。
- 特殊输入测试：输入的链表头节点是nullptr指针。
Java代码
public class Offer052 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
return Solution1(pHead1,pHead2);
}
/**
* 利用长度关系
* @param pHead1
* @param pHead2
* @return
*/
private static ListNode Solution1(ListNode pHead1, ListNode pHead2) {
int listLength1 = getListLength(pHead1);
int listLength2 = getListLength(pHead2);
int dif = listLength1-listLength2;
ListNode longList = pHead1;
ListNode shortList = pHead2;
if(listLength1<listLength2) {
longList = pHead2;
shortList = pHead1;
dif = listLength2-listLength1;
}
for(int i=0;i<dif;i++) {
longList = longList.next;
}
while(longList!=null && shortList!=null && longList!=shortList) {
longList = longList.next;
shortList = shortList.next;
}
ListNode firstCommonFirst = longList;
return firstCommonFirst;
}
private static int getListLength(ListNode pHead1) {
int length = 0;
while(pHead1!=null) {
length++;
pHead1 = pHead1.next;
}
return length;
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}
代码链接
最新文章
- CSS系列：在HTML中引入CSS的方法
- 转载：《TypeScript 中文入门教程》 9、泛型
- ionic入门01
- html EVENT对象
- 在Sqlserver下巧用行列转换日期的数据统计
- JavaScript中产生标识符方式的演变
- 转｛QQ浏览器X5内核问题汇总｝
- HDU 4293 Groups (线性dp)
- JsonUtil对象与json互转
- java利用commons-email发送邮件并进行封装
- 阿里如何实现海量数据实时分析技术－AnalyticDB
- 半导体知识：蚀刻（Etch）工艺讲解
- 快速解决PL/SQL Developer过期问题（无需注册码等复杂操作）
- 在他机上还原DB2的备份
- Leaflet_扩展Leaflet：类（2017-10-26）
- 第1节 常用DOS（磁盘操作系统）命令
- 【CF1132F】Clear the String (DP)
- [uwsgi: command not found]
- C/C++掌握技能（一）
- RPi Desktop盒子安装与服务配置