【チェーンテーブル6】
1291 ワード
【タイトル】2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
【考え方】1両チェーンテーブルの長さを取得する.
2長いチェーンテーブルを先にn歩譲った後、このとき2つのチェーンテーブルの位置が同じになる.
3 2つのチェーンテーブルは、同じ最初の同じノード値が同じになるまで同時に巡回され、最初の共通ノードが返されます.(すでに牛客ACに)
【考え方】1両チェーンテーブルの長さを取得する.
2長いチェーンテーブルを先にn歩譲った後、このとき2つのチェーンテーブルの位置が同じになる.
3 2つのチェーンテーブルは、同じ最初の同じノード値が同じになるまで同時に巡回され、最初の共通ノードが返されます.(すでに牛客ACに)
/*
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;
int len1=getLen(pHead1);
int len2=getLen(pHead2);
int val=len1-len2;
ListNode longNode=pHead1;
ListNode shortNode=pHead2;
if(val<0){
val=-val;
longNode=pHead2;
shortNode=pHead1;
}
for(int i=0;i<val;i++){
longNode=longNode.next;
}
while(longNode!=null &&shortNode!=null){
if(shortNode.val==longNode.val){
return longNode;
}
longNode=longNode.next;
shortNode=shortNode.next;
}
return null;
}
public int getLen(ListNode pHead){
int len=0;
while(pHead!=null){
len++;
pHead=pHead.next;
}
return len;
}
}