public class IntersectionOfTwoLinkedList { /* 解法一:暴力遍历求交点。 时间复杂度:O(m*n) 空间复杂度:O(1) */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null||headB==null) return null; if (headA==headB) return headA; ListNode tempA=headA; ListNode tempB=headB; while (tempA!=null){ tempB=headB; while (tempB!=null){ if (tempA==tempB) return tempA; tempB=tempB.next; } tempA=tempA.next; } return null; } /* 解法二:哈希表求解,思想和解法一差不多,将B存入哈希表,遍历A的节点看是否存在于B 时间复杂度:O(m+n) 空间复杂度:O(m)或O(n) */ public ListNode getIntersectionNode2(ListNode headA, ListNode headB) { if(headA==null||headB==null) return null; if (headA==headB) return headA; Set<ListNode> set=new HashSet<>(); ListNode tempB=headB; while (tempB!=null){ set.add(tempB); tempB= tempB.next; } ListNode tempA=headA; while (tempA!=null){ if (set.contains(tempA)) return tempA; tempA= tempA.next; } return null; } /* 解法三:双指针:当两个链表长度相等时,只需要依次移动双指针,当指针指向的节点相同时,则有交点。 但是问题就在于,两个链表的长度不一定相等,所以就要解决它们的长度差。 一个字概述这个解法:骚。 */ public ListNode getIntersectionNode3(ListNode headA, ListNode headB) { if (headA==null||headB==null) return null; ListNode pA=headA; ListNode pB=headB; while (pA!=pB){ pA=pA==null?headB:pA.next; pB=pB==null?headA:pB.next; } return pA; } }
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!