[数据结构与算法]力扣 160.相交链表 解题总结

【题目】

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

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

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

链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists

【解题思路】

双指针分别指向两个单链表的头节点，然后开始遍历比较，即设p1指向headA，p2指向headB，当p1.next=null时，p1=headB，同理，p2.next=null时，p2=head1，若不相交，那么则p1p2相交的节点为null，若相交，则p1p2相等的节点为第一个相交的节点。

这么说可能不好理解。

此时有两条链表，一条长，一条短，假设长链表长度为a，短链表长度为b，其中共享节点长度为c，那么此时，两条链表到达共享节点起始节点的步数分别为 a-c 和 b-c ，长短链表非共享结点互相拼接，之后的长度分别为 a-c +b 和 b-c +a ，长度相等。
本质上就是长短链表互相拼接之后达到登场 一个长a+b ,一个长b+a，然后拼接两者从头开始遍历必然能够同时到达共享节点。

【代码】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode p1 = headA,p2 = headB;
        while(p1!=p2){
            p1 = p1==null?headB:p1.next;
            p2 = p2==null?headA:p2.next;
        }
        return p1;
    }
}