链表｜ Leetcode 160

Leetcode 分类刷题 —— 链表类（Linked List）

1、题目

Leetcode 160. Intersection of Two Linked Lists

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

2、思路

求两个链表的相交节点，首先要让两个链表从同距离末尾同等距离的位置开始遍历，消除两个链表的长度差可以采用链表合并。
pA走过的路径为：A链+B链
pB走过的路径为：B链+A链
pA、pB走过的长度相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
注意不是判断结点的值相等，而是要判断结点本身是否相等，结点相等意味着结点值和结点地址都得相等才行。

3、Java 代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}