想要精通算法和SQL的成长之路 - 相交链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了想要精通算法和SQL的成长之路 - 相交链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 相交链表（双指针）

原题链接
想要精通算法和SQL的成长之路 - 相交链表,精通算法和SQL之路,算法,链表
思路如下：

1.我们假设 headA链表的长度为 a。headB链表的长度为b。两个链表的公共部分长度为c（如果存在），公共节点为node。

头结点headA到node前，有a-c个节点。
头结点headB到node前，有b-c个节点。

2.那么我们用两个指针，A和B。分别指向两个链表的头节点。

指针A走完链表headA再走链表headB。走到node节点的时候，走过的步数为：a + (b - c)
指针B走完链表headB再走链表headA。走到node节点的时候，走过的步数为：b + (a - c)

首先，两个指针走过的步数一定是相等的，但是对于返回结果而言，我们可以根据c来区分：

如果两个链表存在相交链表，那么c肯定非空，此时指针A或者B都是指向node节点。
如果两个链表无相交部分，那么c的值为0，也就是说此时A或者B的指向是null节点。

因此我们选哪个都可以，最后返回任意一个指针即可，代码如下：文章来源地址https://www.toymoban.com/news/detail-733607.html

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
    	// 如果指针a为null，那么继续遍历headB链表，否则继续遍历headA链表。指针b同理
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }
    return a;
}