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

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

两个链表的交叉

1. 题目

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

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

2. 样例

   下列两个链表：
   
   在节点 c1 开始交叉。

3. 挑战

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

4. 题解

   如样例，对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;}  
}

Last Update 2016.11.11

这篇关于380.Intersection of Two Linked Lists-两个链表的交叉（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---