赞
踩
(leetcode 2490)
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
。
用集合HashSet存放headA节点,先存入,再利用contains()方法判断是否包含。
时间复杂度O(n+m)
- public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
- ListNode temp = headA;
- Set basket = new HashSet();
- while(temp != null) {
- basket.add(temp);
- temp = temp.next;
- }
- temp = headB;
- while(temp != null) {
- if(basket.contains(temp)) return temp;
- temp = temp.next;
- }
- return null;
这方法可太妙了。
链表1和链表2的长度分别为m和n,相交长度为l,如何保证时间复杂度降低的情况下,一步找到交点呢?
规律:
如果temp从链表1开始遍历,到头后接入链表2直到交点,那么temp一共经过了(n+m-l)个节点;
而如果temp先遍历2再遍历1,temp同样经过(n+m-l)个节点。
那么此时,两个temp指向同一个节点,即交点,如果没有交点,那么指向空节点null
- public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
- ListNode temp1 = headA;
- ListNode temp2 = headB;
- while(temp1 != temp2) {
- temp1 = temp1 == null ? headB : temp1.next;
- temp2 = temp2 == null ? headA : temp2.next;
- }
- return temp1;
- }
这方法可太妙了!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。