面试题-链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

题面

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

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

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

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

思路① 先行移动长链表实现同步移动

注意，是求两个链表交点节点的指针，不是数值相等，而是指针相等。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    listNode curA = headA;
    listNode curB = headB;
    int lenA = 0, lenB = 0;
    while (curA != null) { // 求链表A的长度
        lenA++;
        curA = curA.next;
    }
    while (curB != null) { // 求链表B的长度
        lenB++;
        curB = curB.next;
    }
    curA = headA;
    curB = headB;
    // 让curA为最长链表的头，lenA为其长度
    if (lenB > lenA) {
        // 1. swap (lenA, lenB);
        int tmpLen = lenA;
        lenA = lenB;
        lenB = tmpLen;
        // 2. swap (curA, curB)
        ListNode tmpNode = curA;
        curA = curB;
        curB = tmpNode;
    }
    // 求长度差
    int gap = lenA - lenB;
    // 让curA和curB在同一起点上（末尾位置对齐）
    while (gap-- > 0) {
        curA = curA.next;
    }
    // 遍历curA和curB，遇到相同则直接返回
    while (curA != null) {
        if (curA == curB) {
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
}

思路② 合并链表实现同步移动

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	// p1 指向 A 链表头节点，p2 指向 B 链表头节点
	ListNode p1 = headA, p2 = headB;
	while (p1 != p2) {
		// p1 走一步，如果走到 A 链表末尾，转到 B 链表
		if (p1 == null) p1 = headB;
		else p1 = p1.next;
		// p2 走一步，如果走到 B 链表末尾，转到 A 链表
		if (p2 == null) p2 = headA;
		else p2 = p2.next;
	}
	return p1;
}