Problem :

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


My Solution :

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p1, p2 = headA, headB
count = 0
while count < 3:
if p1 is p2:
return p1
if p1 and p1.next:
p1 = p1.next
else:
count += 1
p1 = headB
if p2 and p2.next:
p2 = p2.next
else:
count += 1
p2 = headA
return


Comment :

개인적으로 이런 류의 문제를 좋아하지 않는다. 왜냐하면 한번 풀어봤거나 책에서 본 적이 없는 경우 생각해 내기 힘든 방법이기 때문이다. 물론 set을 이용하면 쉽게 풀 수 있는데 O(1) memory로 풀어보라고 하면 이 방법밖에는 없다. 두 포인터를 각각 전진시키고 끝에 도달하면 반대쪽 출발지점으로 보낸다. 이렇게 하면 교차점이 있는 경우 만날 수 밖에 없다.