博客

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：



题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

1.哈希表解法

2.分别统计从两个链表头到最终结点的结点个数，然后结点个数做差，让结点数多的链表头先走差值数的步数，然后两个链表头一起向前走，并判断两个链表头指向的结点是否相同。

如这题应该是比较明显的双指针题，要是能实现一种算法让两个指针分别从A和B点往C点走，两个指针分别走到C后，又各自从另外一个指针的起点，也就是A指针第二次走从B点开始走，B指针同理，这样，A指针走的路径长度 AO + OC + BO 必定等于B指针走的路径长度 BO + OC + AO，这也就意味着这两个指针第二轮走必定会在O点相遇，相遇后也即到达了退出循环的条件，代码如下：

	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        
        while(A!=B) {
        	if(A==null)
        		A = headB;
        	else
        		A = A.next;
        	
        	if(B==null)
        		B = headA;
        	else
        		B = B.next;
        }
		
		
		return A;
    }