Python solution with detailed explanation


  • 1
    G

    Solution

    Intersection of Two Linked Lists https://leetcode.com/problems/intersection-of-two-linked-lists/?tab=Description

    Algorithm

    • Find the length m and n of the two lists. Then find the difference d = m-n.
    • Now move the longer list head by d.
    • Now move both m and n by 1 at each iteration and return when they meet.
    class Solution:
        # @param two ListNodes
        # @return the intersected ListNode
        def move(self, root, num):
            for i in range(num):
                root = root.next
            return root
        
        def count(self,root):
            cnt = 0
            while root:
                root = root.next
                cnt = cnt+1
            return cnt
            
        def getIntersectionNode(self, headA, headB):
            n = self.count(headA)
            m = self.count(headB)
            d = abs(n-m)
            if m>n:
                headB = self.move(headB, d)
            else:
                headA = self.move(headA, d)
            while True:
                if headA == headB:
                    return headA
                else:
                    headA = headA.next
                    headB = headB.next
    

Log in to reply
 

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