image.png

解法

自己想的算法，整体时间复杂度为o(m+n),空间复杂度为o(1)。找出长度的差值，让两个链表能一起到终点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 找出两个链表相差的长度，以相同的长度位置向后遍历
        int len1 = 0;
        int len2 = 0;
        ListNode temp = headA;
        while (temp != null) {
            len1++;
            temp = temp.next;
        }

        temp = headB;
        while (temp != null) {
            len2++;
            temp = temp.next;
        }

        if (len1 >= len2) {
            int diff = len1 - len2;
            while (diff > 0) {
                headA = headA.next;
                diff--;
            }
        } else {
            int diff = len2 - len1;
            while (diff > 0) {
                headB = headB.next;
                diff--;
            }
        }
        
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

下面这个是官方解法，比较巧妙，利用不相等的长度，走完自己再走对方链表，找到两者相交的点。

image.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }
}