链表相交_链表06

力扣题目链接(opens new window)

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

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

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

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

示例 1：

示例 2：

示例 3：

思路

简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

代码如下：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    	int lenA = 0;
    	ListNode curA = headA;
    	int lenB = 0;
    	ListNode curB = headB;
    	while(curA != null) {
    		lenA++;
    		curA = curA.next;
    	}
    	while(curB != null) {
    		lenB++;
    		curB = curB.next;
    	}
    	int gap = Math.abs(lenA-lenB);
    	if(lenA > lenB) {
    		while(gap-- > 0) {
    			headA = headA.next;
    		}
    	} else {
    		while(gap-- > 0) {
    			headB = headB.next;
    		}
    	}
    	while(headA != null) {
    		if(headA == headB) {
    			return headA;
    		}
    		headA = headA.next;
    		headB = headB.next;
    	}
    }
   }