LeetCode160. Intersection of Two Linked Lists - Python

LeetCode160. Intersection of Two Linked Lists - Python

 

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1.

 

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Each value on each linked list is in the range [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
#교차 값은 8이며, A는 교차점 이전에 2개의 노드, B는 교차점으로부터 3개의 노드를 가짐

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
#교차 값은 2

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
#두 리스트는 교차점 없으므로 null 반환

 

Solution: 

토끼와 거북이 알고리즘(Floyd's Tortoise and Hare algorithm) 을 활용하면 시간복잡도 O(N), 공간복잡도 O(1)에 구현 가능So O(N) for time and O(1) for space.

 

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        aMap = set() #hashMap(hashSet)사용
        
        while headA: #순회하며 set에 각 노드를 넣고
            aMap.add(headA) 
            headA = headA.next
        
        while headB:
            if headB in aMap: #head(로 시작하는 연결리스트가)가 set에 있는지 확인
                return headB
            else:
                headB = headB.next
        return None

 

(참고 사이트)

ryuing.tistory.com/29

allo-ew.tistory.com/98