LeetCode - 160. Intersection of Two Linked Lists (Swift)

 

https://leetcode.com/problems/intersection-of-two-linked-lists/

LeetCode - The World's Leading Online Programming Learning Platform

요약: 두개의 linked list를 순회하면서 교차점을 찾아서 반환하는 문제

 

Set으로 하고 싶은데 안 되고

while headA != nil, headB != nil로 하기엔 길이가 다르니까

count로 비교를 해서 해야할 것 같은데

Hashable, Equatable도 없어서 안 되고..

 

그래서 이것저것 찾아보다가 while문으로 끝까지 돌리면 될거같은데 자꾸 틀려서..

GPT와 함께 해결하였습니다...

---

 

풀이

두개의 리스트를 끝까지 순회하면서 공통된 val를 찾으면 됨

ListNode는 Class로 정의되어 있기 때문에 두개의 리스트를 비교하고 싶다면 참조 연산자를 사용하면 됨

(* 참조연산자란? : https://songios.tistory.com/24 아주 잘 설명해주신 블로그를 가져왔어요)

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
    var listA = headA
    var listB = headB
    
    while listA !== listB {
        listA = (listA == nil) ? headB : listA?.next
        listB = (listB == nil) ? headA : listB?.next
    }
    
    return listA 
}

두개의 list가 동일할 때까지 (값을 찾을 때까지)

list.next로 이동해가면서 탐색하기

여기서 길이가 다름에 대한 처리는 listA == nil?이 true 일때 headB로 이동해줌으로써 해주고 있는 것

 

예제를 보면

let headA: ListNode? = ListNode(4, ListNode(1, ListNode(8, ListNode(4, ListNode(5)))))
let headB: ListNode? = ListNode(5, ListNode(6, ListNode(1, ListNode(8, ListNode(4, ListNode(5))))))

headA = [4, 1, 8, 4, 5]

headB = [5, 6, 1, 8, 4, 5]

 

B의 길이가 A보다 김

이런 경우 해당 while문을 돌때, A가 먼제 nil에 도착함

listA -> 4 -> 1 -> 8 -> 4 -> 5 -> nil
listB -> 5 -> 6 -> 1 -> 8 -> 4 -> 5 -> nil

listA -> 1 -> 8 -> 4 -> 5 -> nil
listB -> 6 -> 1 -> 8 -> 4 -> 5 -> nil

listA -> 8 -> 4 -> 5 -> nil
listB -> 1 -> 8 -> 4 -> 5 -> nil

listA -> 4 -> 5 -> nil
listB -> 8 -> 4 -> 5 -> nil

listA -> 5 -> nil
listB -> 4 -> 5 -> nil

listA -> nil
listB -> 5 -> nil

이런 경우 listA의 head를 listB의 head로 설정하여

끝까지 순회할 수 있도록 하는 것

listA -> 5 -> nil
listB -> 5 -> nil

listA -> nil
listB -> nil

두개의 list가 nil이 되었다는 것은 순회를 다 했다는 것 == while문 종료

이 때 둘 다 nil이면서 교차점이 있다면 listA는 교차점이 head가 되고 그 head를 리턴

 

즉, 교차점 발견 또는 Nil인 경우,

• listA와 listB가 동일한 노드(교차점)를 가리키거나 둘 다 nil이 되면 루프가 중단됨
• 교차점이 있으면 listA가 반환되고 공통 노드가 됨
• 교차점이 없고 둘 다 'nil'이 되면 'nil'이 반환됨

 

 

별거 아닌 문제인제 왜이렇게 어려웠을까요 .. ? ㅠ

더 좋은 방법이 있다면 피드백 부탁드립니다!