0420 TIL

160. Intersection of Two Linked Lists

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        cur=headA
        cur2=headB
        while cur:
            if cur.val==headB.val:
                if cur.next and cur.next.val==headB.next.val:
                    return cur
            else:
                cur=cur.next
        while cur2:
            if headA.val==cur2.val:
                if cur2.next and cur2.next.val==headA.next.val:
                    return cur
            else:
                cur2=cur2.next

원시적으로 반복문을 2개 돌린다 -> 시간 초과

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a= headA
        b= headB
        
        if headA==None or headB==None:
            return None

        while a!=b:
          if a==None:
            a=headB 
          else:
            a=a.next
          if b==None:
            b=headA
          else:
            b=b.next
            
        return a

예외처리를 따로 해주고나서.. 왜 headA를 넣는지 지하철에서 생각해보자!ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:

        if headA==None or headB==None:
            return None

        a = headA
        b = headB

        while a!=b:
            a = headB if a==None else a.next
            b = headA if b==None else b.next
        return a

이건 요약한 거

다른 풀이지만 같은 얘기다
결국에.. 이렇게 한 이유는 .. 계속 순회를 하기 위해서
즉 두 리스트 간 length difference를 없애기 위해서
하나씩 증가하기때문에 while을 두개 써서 비교해야할 거라고 생각했지만
한 리스트가 마지막에 도달했을 때, 다른 리스트를 넣어주면, 인터섹션이 아님에도 불구하고 같은 리스트라서 같은 값이 나오는 예외인 경우가 있을 것 같았으나 길이가 다르기때문에 동시에 같은 리스트의 같은 값이 나올 수는 없다. 근데 만약 최소공배수번 돌면..?
그 전에 인터섹션이 있으면 찾으려나..? 그것은 생각해볼 문제다...

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        l1, l2 = headA, headB# First we are taking two pointers
        while l1!=l2:  # if heads are equal this implies that we found our intersection node and then we`ll return it.
            if l1: # if list1 is there then go ahead.
                l1=l1.next # we traverse to the list to check if we found the intersection node.
            else:
                l1 = headB # if we reach to the end of the list1 then we will move our pointer to the other list head, WHY: - explained separately below.
			# above if condition in comprehension approach. 
            # l1=l1.next if l1 else headB 
            if l2:  # if list2 is there then go ahead.
                l2=l2.next # we traverse to the list to check if we found the intersection node.
            else:
                l2 = headA # if we reach to the end of the list2 then we will move our pointer to the other list head, WHY: - explained separately below.
			# above if condition in comprehension approach. 
            # l2=l2.next if l2 else headA
        return l1 # returning the pointer, we could return l2 also as we found our intersection else null.