49.Intersection of Two Linked Lists

本文主要是介绍49.Intersection of Two Linked Lists，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2↘c1 → c2 → c3↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

分析：题目要求是找到两个单链表最初始的共同节点。

方法一

Step1：统计A和B的长度；

Step2:比较链表A和B的长度，为保证后面的代码统一，如果A的长度比B大，则交换A和B的头结点；

Step3:先让长的B先走|lena-lenb|步；

Step4:让A和B同时走，直到A和B为null，或者遇到A和B相同的节点。

/*找两个单链表的交叉点*/public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//时间复杂度是o(lena+lenb)ListNode A = headA;ListNode B = headB;int lena = 0;int lenb = 0;/*Step1:统计A和B的长度*/while(A!=null){lena++;A=A.next;}A = headA;while(B!=null){lenb++;B=B.next;}B = headB;/*Step2:比较链表A和B的长度，为保证后面的代码统一，如果A的长度比B大，则交换A和B的头结点*/if(lena>lenb){ListNode l = A;A = B;B = l;}/*Step3:先让长的B先走|lena-lenb|步*/for(int i=0;i<Math.abs(lena-lenb);i++){B=B.next;}/*Step4:让A和B同时走，直到A和B为null，或者遇到A和B相同的节点*/while(A!=B){A=A.next;B=B.next;}return B;}

方法二：理论上和我自己测试的都是正确的，但是在leetcode上提交之后却不通过。。。。。。。。。。。。。需要进一步考虑~~~~

 Step1:两个链表同时向后走，找到最先走到链表末尾的节点；

Step2:让最先走到末尾的链表节点指向另外一个链表的头结点，然后判断新的长链表中是否有环，如果有环则返回入口节点，否则返回null。

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {//自己测试通过，但是leetcode提交不通过(暂时还不知道为什么？？？？20151027)ListNode A = headA;ListNode B = headB;ListNode C = new ListNode(0);if(A==null || B==null){return null;}/*Step1:两个链表同时向后走，找到最先走到链表末尾的节点*/while(A.next!=null && B.next!=null){A=A.next;B=B.next;}/*Step2:让最先走到末尾的链表节点指向另外一个链表的头结点，然后判断新的长链表中是否有环，并返回入口节点*/if(A.next == null){A.next = headB;C = detectCycle(headA);}else{B.next = headA;C = detectCycle(headB);}return C;}/*如果一个链表中由环，则返回的是环的入口节点*/public ListNode detectCycle(ListNode head) {/*Step1:先找到链表中是否有环，有环的话通过快指针和慢指针找到其碰撞的节点*/if(head == null || head.next == null){return null;}ListNode slow = head;ListNode fast = head.next;while(fast!=null && fast.next!=null){if(fast == slow){break;}fast = fast.next.next;//每次fast走两步，slow走一步，如果有环，则fast和slow一定相遇slow = slow.next;}if(fast != slow){//fast不等于slow，说明没有环return null;}else{/*Step2:找入口节点：头结点到入口节点的距离等于碰撞点的下一个节点p到入口点的距离+（n-1）c,其中c表中环的长度*/ListNode p = fast.next;//设置p为碰撞点的下一个节点ListNode h = head;while(h!=null && p!=null){if(p == h){break;}h=h.next;p = p.next;}return h; }}

这篇关于49.Intersection of Two Linked Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---