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;}}

具体代码如下