方法1:双指针
时间复杂度:$O(m + n)$
空间复杂度:$O(1)$
解题思路
如果指针pA为空,则将指针pA移到链表headB的头节点;如果指针pB为空,则将指针
pB移到链表headA的头节点。
当指针pA和pB指向同一个节点或者都为空时,返回它们指向的节点或者null。
Java 代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}