3
#yyds干货盘点# 面试必刷TOP101：两个链表的第一个公共结点
source link: https://blog.51cto.com/u_15488507/5539690
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：两个链表的第一个公共结点
原创1.简述：
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： 要求：空间复杂度 ，时间复杂度
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1
{1,2,3},{4,5},{6,7}
{6,7}
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
{1},{2,3},{}
2个链表没有公共节点 ,返回null，后台打印{}
2.代码实现：
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while(l1 != l2){
l1 = (l1==null)?pHead2:l1.next;
l2 = (l2==null)?pHead1:l2.next;
}
return l1;
}
}
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while(l1 != l2){
l1 = (l1==null)?pHead2:l1.next;
l2 = (l2==null)?pHead1:l2.next;
}
return l1;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK