160.相交链表

题目地址： https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

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

如下面的两个链表：

示例1

在节点 c1 开始相交。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

如果两个链表有交集，按标记走完就能找到交集点： a + c + b = b + c + 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 pa = headA;
        ListNode pb = headB;
        //用来标记是否循环到链表尾部
        boolean flagA = false;
        boolean flagB = false;
        while(pa != pb){
            pa = pa.next;
            pb = pb.next;

            if(pa == null){
                if(flagA && flagB){ //两个链表都已经到过尾部，依然没有找到相交点，表示链表并没有相交
                    return null;
                }
                //将指针A挪到B链上
                pa = headB;
                //A链遍历结束
                flagA = true;
            }

            if(pb == null){
                if(flagA && flagB){ //两个链表都已经到过尾部，依然没有找到相交点，表示链表并没有相交
                    return null;
                }
                //将指针B挪到A链上
                pb = headA;
                //B链遍历结束
                flagB = true;
            }
        }
        //相同值表示相交了
        return pa;

    }
}