Java找出两个链表的第一个公共节点

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述
输入两个链表，找出它们的第一个公共结点。

我的思路：因为是链表，长度都是未知的，不能盲目的两个一起开始自增判断。

首先需要得到 L1的长度和 L2的长度，让较长的那个先走（length1-length2）步。然后再一直next去判断。

AC代码， 34ms,503K

/*
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==pHead2){
return pHead1;
} int l1=getLength(pHead1);
int l2=getLength(pHead2);
if(l1>l2){
for(int i=;i<(l1-l2);i++){
pHead1=pHead1.next;
} }else{
for(int i=;i<(l1-l2);i++){
pHead2=pHead2.next;
}
} boolean f=true;
ListNode p=null;
while(f){
if(pHead1==null||pHead2==null){
return null;
}
if(pHead1==pHead2){
p=pHead1;
f=false;
}else{
pHead1=pHead1.next;
pHead2=pHead2.next;
} } return p;
}public static int getLength(ListNode pHead) {
        int length = ;

        ListNode current = pHead;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }
}

看看别的思路：

1、用HashMap:

第一个while是把pHead1的所有节点都放进去。

第二个while开始，对pHead2的每个节点都用 containsKey 方法来判断。

因为在前一种思路中，要求得两个链表的长度就需要对两个链表进行一次遍历，用HashMap的方法其实更加节省时间。

33ms,503K

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 current1 = pHead1;
        ListNode current2 = pHead2;

        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }

        return null;

    }
}