一、题目
输入描述:
输入分为是3段,第一段是第一个链表的非公共部分,第二段是第二个链表的非公共部分,第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表,并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面,用户得到的输入只有pHead1和pHead2。
二、题解
2.1 解法一 、双指针循环
使用两个指针N1,N2,一个从链表1的头节点开始遍历,我们记为N1,一个从链表2的头节点开始遍历,我们记为N2。
让N1和N2一起遍历,当N1先走完链表1的尽头(为null)的时候,则从链表2的头节点继续遍历,同样,如果N2先走完了链表2的尽头,则从链表1的头节点继续遍历,也就是说,N1和N2都会遍历链表1和链表2。
因为两个指针,同样的速度,走完同样长度(链表1+链表2),不管两条链表有无相同节点,都能够到达同时到达终点。
(N1最后肯定能到达链表2的终点,N2肯定能到达链表1的终点)。
所以,如何得到公共节点:
- 有公共节点的时候,N1和N2必会相遇,因为长度一样嘛,速度也一定,必会走到相同的地方的,所以当两者相等的时候,则会第一个公共的节点
- 无公共节点的时候,此时N1和N2则都会走到终点,那么他们此时都是null,所以也算是相等了。
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;
}
2.2 解法二、集合set
做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中,然后遍历第二个链表的每一个节点,判断在集合set中是否存在,如果存在就直接返回这个存在的结点。如果遍历完了,在集合set中还没找到,说明他们没有相交,直接返回null即可
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) {
//创建集合set
Setset = new HashSet<>();
//先把链表1的结点全部存放到集合set中
while (pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
//然后访问链表2的结点,判断集合中是否包含链表2的结点,如果包含就直接返回
while (pHead2 != null) {
if (set.contains(pHead2))
return pHead2;
pHead2 = pHead2.next;
}
//如果集合set不包含链表2的任何一个结点,说明没有交点,直接返回null
return null;
}
}