解法1：双指针法
创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8->9->5->6。短链表的指针p1会先到达尾部，然后重新指向长链表头部，当长链表的指针p2到达尾部时，重新指向短链表头部，此时p1在长链表中已经多走了k步(k为两个链表的长度差值)，p1和p2位于同一起跑线，往后遍历找到相同节点即可。其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。
时间复杂度：O(m+n), m，n分别为链表A，B的长度，
最坏情况下，公共结点为最后一个，需要遍历m+n个结点
空间复杂度：O(1)
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null){
return null;
}
ListNode p1=pHead1;
ListNode p2=pHead2;
while(p1!=p2){
p1 = p1==null ? pHead2 : p1.next;
p2 = p2==null ? pHead1 : p2.next;
}
return p1;
}解法2：哈希
使用HashSet，解决有环无环，相交不相交的情况
import java.util.HashSet;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null){
return null;
}
HashSet<ListNode> set1=new HashSet<>();
HashSet<ListNode> set2=new HashSet<>();
while(pHead1!=null && !set1.contains(pHead1)){
set1.add(pHead1);
pHead1=pHead1.next;
}
while(pHead2!=null && !set2.contains(pHead2)){
set2.add(pHead2);
if(set1.contains(pHead2)){
return pHead2;
}
pHead2=pHead2.next;
}
return null;
}
}解法3：栈
我们发现，公共部分一定是在尾部，如果我们从后面开始找会更快，最后一个相同点就是我们要找的点，不过这是单向链表，所以我们想到了栈的结构——后进先出
解法4：求差法
其实我们用栈，只是为了想同时能到达两个链表的尾节点。当两链表长度不同时，我们从头开始遍历，到后面的时间就不一致。我们可以先遍历两个链表，得到它们的长度，然后，链表长的先走先走多的几个节点，接着同时在两个链表遍历，找到的第一个相同点就是我们要找的第一个公共点
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null) return null;
// 求两链表的长度
int count1 = 0;
ListNode p1 = pHead1;
while(p1 != null) {
p1 = p1.next;
count1++;
}
int count2 = 0;
ListNode p2 = pHead2;
while(p2 != null) {
p2 = p2.next;
count2++;
}
// 将长链表的指针移动到和短链表相同长度的位置
int flag = count1-count2;
if(flag > 0) {
while(flag > 0) {
pHead1 = pHead1.next;
flag--;
}
while(pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}
else {
flag = -flag;
while(flag > 0) {
pHead2 = pHead2.next;
flag--;
}
while(pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead2;
}
}
}有环思路：较为麻烦
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode loop1 = getLoopNode(pHead1);
ListNode loop2 = getLoopNode(pHead2);
if (loop1 == null && loop2 == null) {
return noLoop(pHead1, pHead2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(pHead1, loop1, pHead2, loop2);
}
return null;
}
private ListNode getLoopNode(ListNode pHead) {
if (pHead == null || pHead.next == null || pHead.next.next == null) {
return null;
}
ListNode n1 = pHead.next;
ListNode n2 = pHead.next.next;
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n1 = n1.next;
n2 = n2.next.next;
}
n2 = pHead;
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
private ListNode noLoop(ListNode pHead1, ListNode pHead2) {
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
int n = 0;
while (cur1.next != null) {
cur1 = cur1.next;
n++;
}
while (cur2.next != null) {
cur2 = cur2.next;
n--;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? pHead1 : pHead2;
cur2 = cur1 == pHead1 ? pHead2 : pHead1;
n = Math.abs(n);
while (n != 0) {
cur1 = cur1.next;
n--;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
private ListNode bothLoop(ListNode pHead1, ListNode loop1, ListNode pHead2, ListNode loop2) {
ListNode cur1 = null;
ListNode cur2 = null;
if (loop1 == loop2) { //先相交，在共享同一个环
cur1 = pHead1;
cur2 = pHead2;
int n = 0;
while (cur1 != loop1) {
cur1 = cur1.next;
n++;
}
while (cur2 != loop2) {
cur2 = cur2.next;
n--;
}
cur1 = n > 0 ? pHead1 : pHead2;
cur2 = cur1 == pHead1 ? pHead2 : pHead1;
n = Math.abs(n);
while (n != 0) {
cur1 = cur1.next;
n--;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) { //在环的某处相遇
return loop1;
}
cur1 = cur1.next;
}
return null; //各自成环
}
}
京公网安备 11010502036488号