Leetcode 题目解析之 Intersection of Two Linked Lists

原创

ruochen

发布于 2022-01-14 11:35:59

1.2K0

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.d
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

记链表A的长度是lenA，最后一个结点为p；链表B的长度是lenB，最后一个结点为q。
如果p≠q，则链表A、B不相交，直接返回null。因为如果链表A、B在某处相交，那么后面的结点完全相同（如题目中所示，是Y型的）。
如果p=q，则链表A、B在某处相交。让长的链表走|lenA−lenB|步（按照末端对齐），然后两个链表同时向前走，相等结点即为相交公共结点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    if (headA == null || headB == null) {
        return null;
    }

    // 计算链表A的长度
    int lenA = 1;
    ListNode p = headA;
    while (p.next != null) {
        lenA++;
        p = p.next;
    }

    // 计算链表B的长度
    int lenB = 1;
    ListNode q = headB;
    while (q.next != null) {
        lenB++;
        q = q.next;
    }

    // 若A和B的最后一个结点不等，则不相交，返回null
    if (p != q) {
        return null;
    }

    // 链表按照尾部对齐
    if (lenA > lenB) {
        int t = lenA - lenB;
        while (t-- != 0) {
            headA = headA.next;
        }
    } else {
        int t = lenB - lenA;
        while (t-- != 0) {
            headB = headB.next;
        }
    }

    // 同时向前走
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法