380.Intersection of Two Linked Lists-两个链表的交叉（中等题）

本文主要是介绍380.Intersection of Two Linked Lists-两个链表的交叉（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两个链表的交叉

题目

请写一个程序，找到两个单链表最开始的交叉节点。

注意事项
如果两个链表没有交叉，返回null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
样例

下列两个链表：

在节点 c1 开始交叉。
挑战

需满足 O(n) 时间复杂度，且仅用 O(1) 内存。
题解

如样例，对A，B进行遍历得到A的节点数为5，B的节点数为6，则先将B向后移动1个节点，则此时A，B长度相同。再将A，B同时向后移动，并比较节点是否相同，如果相同则返回该节点。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;      *     }* }*/
public class Solution {/*** @param headA: the first list* @param headB: the second list* @return: a ListNode */public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode n1 = headA;ListNode n2 = headB;int count1 = 0;int count2 = 0;while (n1 != null){count1++;n1 = n1.next;}while (n2 != null){count2++;n2 = n2.next;}if (count1 < count2){ListNode tmp = headA;headA = headB;headB = tmp;}int n = Math.abs(count1 - count2);while (n-- > 0){headA = headA.next;}while (headA != null){if (headA.val == headB.val){return headA;}headA = headA.next;headB = headB.next;}return null;}  
}