160. Intersection of Two Linked Lists 「相交链表」

编写一个程序可以找出两个单向链表的的第一个相交的节点。

例如,下图的两个链表:

在 c1 节点开始相交。

例一:

输入: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出: 值为 8 的节点。
输入解释: 相交节点的值是 8(如果两个链表相交这个值一定不为 0)。从 A 的头部开始,A 可以表示为 [4,1,8,4,5]。从 B 的头部开始,B 可以表示为 [5,0,1,8,4,5]。A 在相交节点前有 2 个节点,B 在相交节点前有 3 个节点。

例二:

输入: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出: 值为 2 的节点。
输入解释: 相交节点的值是 2(如果两个链表相交这个值一定不为 0)。从 A 的头部开始,A 可以表示为 [0,9,1,2,4]。从 B 的头部开始,B 可以表示为 [3,2,4]。A 在相交节点前有 3 个节点,B 在相交节点前有 1 个节点。

例三:

输入: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出: null
输入解释: 从 A 的头部开始,A 可以表示为 [2,6,4]。从 B 的头部开始,B 可以表示为 [1,5]。因为两个链表没有相交,intersectVal 一定是 0,同时 skipAskipB 可以为任意值。
解释: 两个链表没有相交,所以返回 null

提示:
1. 如果两个链表没有相交,返回 null
2. 在函数返回结果后,两个链表必须保持原有结构。
3. 你可以认定在链表中不存在循环链表。
4. 你的代码的时间复杂度应当为 O(n),空间复杂度为 O(1)

这个题和环形链表有点异曲同工,也是在走过的距离上做文章。使用双指针,第一个指针在第一个链表上走完之后走第二个链表,第二个指针在第二个链表上走完之后走第一个链表,这样,如果有相交节点两个指针一定会在某个时刻指向同一个节点,而没有相交时两个指针则会同时指向 null,也正好是我们需要的结果。

/*
 * 160. Intersection of Two Linked Lists
 * https://leetcode.com/problems/intersection-of-two-linked-lists/
 * https://www.whosneo.com/160-intersection-of-two-linked-lists/
 */
public class GetIntersectionNode {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(4);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(8);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(0);
        head2.next.next = new ListNode(1);
        head2.next.next.next = head1.next.next;

        GetIntersectionNode solution = new GetIntersectionNode();

        ListNode node = solution.getIntersectionNode(head1, head2);
        if (node != null)
            System.out.println(node.val);
    }

    private ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;

        while (nodeA != nodeB) {
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }

        return nodeA;
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注