LeetCode刷题实战160：相交链表-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 相交链表，我们先来看题面：

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

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

题意

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

样例

解题

https://blog.csdn.net/u010189239/article/details/88947594

思路：

1.链表判空

2.设置pa从headA开始，设置pb从headB开始

3.pa，pb同时向后移动，直到两者有一个为空则结束，表示无交点

4.在3循环中，如果出现pa相遇pb，则此处为交点

5.pa和pb后移一位

6.如果pa和pb均换路且都到达尾部，则表示无交点

7.在3循环中，如果pa到达尾部，则换路从headB开始后移；如果pb到达尾部，则换路从headA开始后移，注：换路只换一次

8.无交点则返回空

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.
        if(headA==null||headB==null){
            return null;
        }
        //2.
        ListNode pa=headA;
        ListNode pb=headB;
        boolean isPaChange=false;
        boolean isPbChange=false;
        //3.
        while(pa!=null&&pb!=null){
            //4.
            if(pa==pb){
                return pa;
            }
            //5.
            pa=pa.next;
            pb=pb.next;
            //6.
            if(isPaChange&&isPbChange&&pa==null&&pb==null){
                break;
            }
            //7.
            if(pa==null){
                pa=headB;
                isPaChange=true;
            }
            if(pb==null){
                pb=headA;
                isPbChange=true;
            }
        }
        //8.
        return null;
    }
}