LeetCode-第160题-相交链表

1.题目描述

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

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

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

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

2.样例描述

3.思路描述

消除两个链表的长度差：指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历；如果 pA 到了末尾，则 pA = headB 继续遍历；如果 pB 到了末尾，则 pB = headA 继续遍历；比较长的链表指针指向较短链表head时，长度差就消除了。如此，只需要将最短链表遍历两次即可找到位置

（思路来源于网站大神）

4.代码展示

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果任一链表为空，直接返回 null
        if (headA == null || headB == null) return null;
        // 初始化两个指针，分别指向链表 headA 和 headB 的头节点
        ListNode pa = headA, pb = headB;
        // 进行循环，直到找到交点或者两个链表都走到尽头
        while (pa != pb) {
            // 如果 pa 走到尽头，则将其重定向到 headB，否则继续向下一个节点移动
            pa = (p服务器托管网a == null) ? headB : pa.next;
            // 如果 pb 走到尽头，则将其重定向到 headA，否则继续向下一个节点移动
            pb = (pb == null) ? headA : pb.next;
        }
        // 返回找到的交点，如果没有交点则返回 null
   服务器托管网     return pa;
    }
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 2024 最热门开源 GitOps 工具盘点

【直播预告】国产数据库，一半都是花架子？” GitOps 是一种侧重于自动化、协作和持续交付的基础设施管理现代方法。它的核心理念是将 Git 作为配置和代码的唯一真理源。在 GitOps 实践中，对基础设施的任何更改都必须通过 Pull Request（合并请…