java with O(n) time complexity and O(1) space complexity


  • 0
    M

    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //ListNode res;
    if(headA==null || headB==null) return null;
    // get length of every list
    int lena = getlen(headA);
    int lenb = getlen(headB);
    if(lena < lenb) {
    return helper(headA, headB, lena, lenb);
    } else {
    return helper(headB, headA, lenb, lena);
    }
    }
    public int getlen(ListNode node) {
    int count = 0;
    while(node != null) {
    count++;
    node = node.next;
    }
    return count;
    }
    public ListNode helper(ListNode headA, ListNode headB, int lena, int lenb) {
    for(int i = 0; i < lenb-lena; i++) {
    headB = headB.next;
    }
    while(headA!=null && headB!=null && headA != headB) {
    headA = headA.next;
    headB = headB.next;
    }
    return headA;
    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.