I cannot figure out what's wrong with my code. My idea should give O(n) time and O(1) space.


  • 0
    J
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    def getLen(head):
        count = 0
        current = head
        while(current):
            count+=1
            current = current.next
        return count
    class Solution:
        # @param two ListNodes
        # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            if  (headA == None) or ( headB == None):
                return None
            gap = getLen(headA)- getLen(headB)
            current1, current2 = headA, headB
            if gap>0:
                while gap>0:
                    current1 = current1.next
                    gap = gap - 1
            elif gap<0:
                while gap<0:
                    current2 = current2.next
                    gap = gap + 1
    
            while(current1 != None and current2 !=None):
                if current1  == current2 :
                    return current1
                else:
                    current1 = current1.next
                    curretn2 = current2.next
            return None
    

    My idea is to start comparing at the (n-k)-th node where k is the number of nodes in the shorter list.
    It says I cannot pass this test case:

    {2,3,4,6,7,8,9} {5,6,7,8,9} \
    Expected: 6\
    Mine: No interaction

    Could anyone help me figure out why this solution doesn't work?


Log in to reply
 

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