Leetcode160 两个链表是否相交

? ?leetcode 160题，判断两个链表是否相交

此题可以说是算法界第一深情，如果我走过你走过的路，那么我们就可能会相遇。

具体解决思路如下

两个链表是否相交有两种可能，一种不相交，一种相交，首先来看下相交的情况，那么它们会有公共部分，假设公共部分长度为c,然后链表一中不想交部分为a, 链表二中不想交部分为b,那么链表一的长度可以表示为a + c, 链表2的长度为b + c, 想在弄两个指针，一个指针A指向链表一的头部，另一个指针B指向链表b的头部，两个指针向后遍历，如果到达了尾部，那么就从另一个链表的头部开始遍历，直到两个节点相同，即找到了交叉节点，那么指针A就走过了a+c +b的长度，指针B走过了b+c +a的长度，可以看到它们是一样大的，所以可以找到相同的节点，同理，如果两个链表不想交，那么都走完两个链表后，节点都为null，代表没有交点。

/**
 * 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) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA != tempB){
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }
}

具体代码如下