fishercoderLeetcode/EASY/src/easy/IntersectionofTwoLinkedLists.java at master · stevesun112/fishercoderLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package easy;

import classes.ListNode;

public class IntersectionofTwoLinkedLists {
    /**Looked at this post: https://discuss.leetcode.com/topic/5492/concise-java-solution-o-1-memory-o-n-time*/

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = findLen(headA), lenB = findLen(headB);
        while (lenA < lenB){
            headB = headB.next;
            lenB--;
        }

        while (lenB < lenA){
            headA = headA.next;
            lenA--;
        }

        while (headA != headB){
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
    }

    private int findLen(ListNode head){
        int len = 0;
        while (head != null){
            head = head.next;
            len++;
        }
        return len;
    }

}