题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
首先计算出两个链表的长度,求长度之差,先让长度长的走差值个步数,然后前后两个指针一块向前走,到两个指针指向的值相同。
public class Solution {
public int lengthOfListnode(ListNode head){
if (head==null) return 0;
int length = 0;
while(head!=null){
length++;
head=head.next;
}
return length;
}
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length_1 = lengthOfListnode(pHead1);
int length_2 = lengthOfListnode(pHead2);
if(length_2>length_1){
ListNode temp = pHead1;
pHead1=pHead2;
pHead2=temp;
}
int minus = Math.abs(length_1-length_2);
ListNode fast=pHead1;
ListNode slow=pHead2;
for (int i=0;i<minus;i++){
fast = fast.next;
}
while(fast!=null&&slow!=null){
if(fast.val==slow.val){
return fast;
}
fast = fast.next;
slow = slow.next;
}
return null;
}
}