leetcode 160. Intersection of Two Linked Lists

题意

判断两个链表是否存在相同的一段链表，如果有就返回该相同的链条，没有返回null

能做到效率为O(n) 空间复杂度为O(1)

我的思路

和判断循环的链表一样使用HashSet，需要开辟O(n)的空间，以及O(n+m)的效率

我的代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode result = null;
        ListNode aTemp = headA,bTemp = headB;
        Set<ListNode> set = new HashSet<ListNode>();
        while(aTemp!=null){
           set.add(aTemp);
           aTemp = aTemp.next ;
        }
        while(bTemp!=null){
            if(set.contains(bTemp))return bTemp;
            bTemp = bTemp.next;
        }
        return result;
    }
}

大神代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode b = headB;
        while (b.next != null) {
            b = b.next;
        }
        b.next = headB;
        ListNode t = headA, h = headA;
        while (h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            if (t == h) {
                t = headA;
                while (t != h) {
                    t = t.next;
                    h = h.next;
                }
                b.next = null;
                return t;
            }
        }
        b.next = null;
        return null;
    }
}

不知道说什么了，引用一下别人的评论吧

Clever, the two iterations will both run for listA.length + listB.length and will reach the intersection point at the same time after switching the pointer.

This is a very clever and easy to read solution. You da man!

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) return null;

    ListNode a = headA;
    ListNode b = headB;

    //if a & b have different len, then we will stop the loop after second iteration
    while( a != b){
    	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;    
    }

    return a;
}

赏

谢谢你请我吃糖果