剑指offer最优解Java版-两个链表的第一个公共结点
2019-07-01 本文已影响4人
全菜工程师小辉
题目描述
输入两个链表,找出它们的第一个公共结点。
解决方法
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 length1 = getLength(pHead1);
int length2 = getLength(pHead2);
// 两链表的长度差
// 如果链表1的长度大于链表2的长度
if (length1 >= length2) {
int len = length1 - length2;
// 先遍历链表1,遍历的长度就是两链表的长度差
while (len > 0) {
pHead1 = pHead1.next;
len--;
}
}
// 如果链表2的长度大于链表1的长度
else if (length1 < length2) {
int len = length2 - length1;
// 先遍历链表1,遍历的长度就是两链表的长度差
while (len > 0) {
pHead2 = pHead2.next;
len--;
}
}
// 开始齐头并进,直到找到第一个公共结点
while(pHead1!=pHead2){
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return pHead1;
}
// 求指定链表的长度
public static int getLength(ListNode pHead) {
int length = 0;
while (pHead != null) {
length++;
pHead = pHead.next;
}
return length;
}
}
复杂度分析:
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。