160. Intersection of Two Linked Lists

yPhantom 2019年10月14日 24次浏览

Write a program to find the node at which the intersection of two singly linked lists begins.

题目链接

Solution

这道题其实和判断一个链表中有没有环是一个道理,我们人为制造一个环,最终它们的相遇的点就是交点。

当a从headA出发,走到末尾的时候再从headB继续走,b同理。那么它们的速度一致,最后的交点就是遇到的点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null ) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while(a != b) {
            a = a == null? headB : a.next;
            b = b == null? headA : b.next;
        }
        return a;
    }
}