160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists:

1
2
3
4
5
A:          a1  a2
                   
                     c1  c2  c3
                               
B:     b1  b2  b3

begin to intersect at node c1. Notes: * If the two linked lists have no intersection at all, return null. * The linked lists must retain their original structure after the function returns. * You may assume there are no cycles anywhere in the entire linked structure. * Your code should preferably run in O(n) time and use only O(1) memory.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode pointA = headA;
        ListNode pointB = headB;
        while(pointA!=pointB){
            pointA = pointA == null ? headB : pointA.next;
            pointB = pointB == null ? headA : pointB.next;
        }
        return pointA;
    }
}

找公共起始点: - 核心问题是两条链路长度不一样怎么办? - 我的写法是写计数两个指针到null的值,然后让其中一个先走几步,但是显然有点蠢 - 答案的方法很妙,如果两者长度相同,不会超时额外操作;如果不用的话根据x+y=y+x的原理,走完自己这里的链路再走对方的链路,总长度一定一样,一定能找到