描述
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
数据范围:n<=1000
要求:空间复杂度 O(1),时间复杂度 O(n)
思路1:统计两个链表长度
先分别统计两个链表长度,让长的先走,直到两个链表长度相等,再同时开始
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//统计两个链表长度
int count1 = getCount(pHead1);
int count2 = getCount(pHead2);
int distance = count2 - count1;
//链表长的先走,直到在同一起跑线
if(distance > 0) {
while(distance != 0) {
pHead2 = pHead2.next;
distance--;
}
} else if(distance < 0){
while(distance != 0) {
pHead1 = pHead1.next;
distance++;
}
}
//同时开始
while(pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}
private int getCount(ListNode node) {
int count = 0;
while(node != null) {
node = node.next;
count++;
}
return count;
}
}
思路2:p1 + p2 = p2 + p1
双指针,链表1遍历完之后继续遍历链表2,链表2遍历完后继续遍历链表1,直到两个指针到达同一个节点
例如:4为公共节点,{1, 2, 4} + {3, 4} = {3, 4} + {1, 2, 4}
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2) {
p1 = p1 != null ? p1.next : pHead2;
p2 = p2 != null ? p2.next : pHead1;
}
return p1;
}
}
思路3:集合Set
链表1遍历放入Set,链表2遍历查找Set中是否包含
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
Set<ListNode> set = new HashSet<>();
while(pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
while(pHead2 != null) {
if(set.contains(pHead2)) {
return pHead2;
}
pHead2 = pHead2.next;
}
return null;
}
}