160. Intersection of Two Linked Lists

三刷 05/2022

Version #3 Two Pointers

注意一开始写了一个bug

就是应该在pA == null的时候使pA指向headB而不是在pA.next == null的时候，否则最后一个点永远不会落入pA == pB的check里面

Time O(M + N)

Space O(1)

Runtime: 1 ms, faster than 99.09% of Java online submissions for Intersection of Two Linked Lists.

Memory Usage: 45.1 MB, less than 89.30% of Java online submissions for Intersection of Two Linked Lists.

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode pA = headA, pB = headB;

        while (pA != pB) {

            pA = pA == null ? headB : pA.next;

            pB = pB == null ? headA : pB.next;

        }

        return pA;

    }

}

Sol #1 HashSet
Time Complexity O(m + n)?
Space Complexity O(m) or O(n)


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


Sol #2 Find the length of each list
If their tail equals to each other, let the longer list go (len2 - len1) steps first
class ResultType {
    public int length;
    public ListNode tail;
    public ResultType(int length, ListNode tail) {
        this.length = length;
        this.tail = tail;
    }
}
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ResultType resA = getInfo(headA);
        ResultType resB = getInfo(headB);
        if (resA.tail != resB.tail) {
            return null;
        }
        int lengthA = resA.length;
        int lengthB = resB.length;
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

    public ResultType getInfo(ListNode head) {
        int length = 1;
        while (head.next != null) {
            head = head.next;
            length++;
        }
        return new ResultType(length, head);
    }
}

【二刷】
14.81 %
一刷写的是什么鬼？
Time O(length of the longer list)
Space O(1)
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int sizeA = getSize(headA);
        int sizeB = getSize(headB);
        ListNode currA = headA, currB = headB;
        while (sizeA > sizeB) {
            currA = currA.next;
            sizeA--;
        }
        while (sizeB > sizeA) {
            currB = currB.next;
            sizeB--;
        }
        while (currA != null && currB != null) {
            if (currA == currB) return currA;
            currA = currA.next;
            currB = currB.next;
        }
        return null;
    }
    //getSize() return the length of the list
    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
}


Sol #3 Go through the same length of path
A: pointA            a1 → a2
                                    ↘dist1     dist3
                                       c1 → c2 → c3
                                    ↗dist2            
B: pointB    b1 → b2 → b3
Let  pointA go to c3 then go back to headB
Let  pointB go to c3 then go back to headA
Since both of them have walked the distance of dist1 + dist2 + dist3
The point that they meet each other is the intersection point
二刷
精髓在于每次都是先跳到null然后再跳回到另一条的head
这样如果两条没有intersection的时候， 当他们都走了全部path的时候，某一时刻两个curr都是null
此时返回任意curr都可以

100.00 %
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode currA = headA;
        ListNode currB = headB;
        //           cB   
        // a1 -> a2
        //                 cA       
        // b1 -> b2 -> b3
        while (currA != currB) {
            currA = currA == null ? headB : currA.next;
            currB = currB == null ? headA : currB.next;
        }
        return currA;
    }
}


一刷
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        ListNode tailA = null;
        ListNode tailB = null;
        while (true) {
            if (pA == null) {
                pA = headB;
            }
            if (pB == null) {
                pB = headA;
            }
            if (pA.next == null) {
                tailA = pA;
            }
            if (pB.next == null) {
                tailB = pB;
            }
       
            if (tailA != null && tailB != null && tailA != tailB) {
                return null;
            }
            if (pA == pB) {
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }
    }
}