思路
快慢指针,链表长度不同时抵消掉多余的长度。
若链表长度不同,则一定时在长链表的链尾相遇。
时间复杂度O(n),空间复杂度O(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 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2) {
// 判断的位置和处理比较关键,整个循环过程两个指针的间隔并不是全程不变的。
p1 = p1 == null ? pHead2 : p1.next;
p2 = p2 == null ? pHead1 : p2.next;
}
return p1;
}
}
笔记
链表长度不同时,会有两次指针换链,每次换链时会导致正在换链的指针慢一步,各换链一次则步数抵消,且相遇时是在短链表的链首。