两个链表的第一个公共节点

题目描述

输入两个链表,找出它们的第一个公共结点。

分析

先遍历一遍分别算出两个链表的长度。算出长度差mins。
较长的链表先走mins步,然后两个链表同时走。

代码:

/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int count1 = 0, count2 = 0;
ListNode ln1 = pHead1, ln2 = pHead2;
while (ln1 != null){
count1++;
ln1 = ln1.next;
}
while (ln2 != null){
count2++;
ln2 = ln2.next;
}
int mins = count1 - count2;
ln1 = pHead1;
ln2 = pHead2;
if (mins > 0){
while (mins > 0){
ln1 = ln1.next;
mins--;
}
}
if (mins < 0){
mins = -mins;
while (mins > 0){
ln2 = ln2.next;
mins--;
}
}
while(ln1 != null && ln1 != ln2){
ln1 = ln1.next;
ln2 = ln2.next;
}
return ln1;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :