[LeetCode][Python3] 160. Intersection of Two Linked Lists

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로 풀어보라고 하면 이 방법밖에는 없다. 두 포인터를 각각 전진시키고 끝에 도달하면 반대쪽 출발지점으로 보낸다. 이렇게 하면 교차점이 있는 경우 만날 수 밖에 없다.