Javaは2つのチェーンの最初の共通ノードを探します。
10900 ワード
, 。
: , , 。
L1 L2 , (length1-length2) 。 next 。
考え方1/*
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=0;i<(l1-l2);i++){
pHead1=pHead1.next;
}
}else{
for(int i=0;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 = 0;
ListNode current = pHead;
while (current != null) {
length++;
current = current.next;
}
return length;
}
}
考え方2 :
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;
}
}