Got runtime error with input {} {}


  • 0
    W

    The algorithm I used is pretty straightforward:

    if len_a < len_b, b will go forward (len_b - len_a) nodes and then a and b start to go forward together until they meet together or to the tail node (return null).

    but I got a runtime error which I don't know why. Any suggestions?

    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None
        lena= self.listlen(headA)
        lenb= self.listlen(headB)
        if lenb < lena: (headA, headB) = (headB, headA)
        delta = lenb - lena
        for i in range(delta):
            headB = headB.next
        while True:
            if headA is None or headB is None:
                return None
            if headA==headB:
                return headA
            headA = headA.next
            headB = headB.next
            
    def listlen(self, ahead):
        if ahead is None:
            return 0
        return 1 + self.listlen(ahead.next)

  • 1
    S

    I've probably 1% knowledge on Python, but I see some obvious things that I want to point out. the listlen routine is a recursive routine. Do you really need to make it recursive? You can just put a simple while loop

    def listlen(ahead):
        len = 0
        while ahead is not None:
            len = len + 1
            ahead = ahead.next
        return len
    

    I don't see the error once I change it to a while loop. As I don't know much about python, I can't comment on this change in behavior further.

    The next comment is about the following line

    delta = lenb - lena
    for i in range(delta):
        headB = headB.next
    

    In the above block if lena is more that lenb, delta will become -ve. In that case the line inside the for loop will never execute.

    Here's how the code looks now

    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            if headA is None or headB is None:
                return None
            lena= self.listlen(headA)
            lenb= self.listlen(headB)
            if lenb < lena: (headA, headB) = (headB, headA)
            delta = lenb - lena
            if delta < 0: delta = 0 - delta
            for i in range(delta):
                headB = headB.next
            while True:
                if headA is None or headB is None:
                    return None
                if headA==headB:
                    return headA
                headA = headA.next
                headB = headB.next
            
        def listlen(self, ahead):
            len = 0
            while ahead is not None:
                len = len + 1
                ahead = ahead.next
            return len
    

Log in to reply
 

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