링크드 리스트의 겹침 유무 확인법 (파이썬, 변수참조, 메모리참조)
링크드 리스트의 겹침 유무 확인법 (파이썬, 변수참조, 메모리참조) — #LeetCode #개발자의도구들 #파이썬참조 #파이썬변수참조 #파이썬메모리참조 only 파이썬 목표 참고 : 여...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들 #파이썬참조 #파이썬변수참조 #파이썬메모리참조
- only 파이썬
- 목표 참고 : 여기
Linked List가 겹치는 구간 찾기
LeetCode(esay 160. Intersection of Two Linked Lists) 60.2%
- c1 Node를 return 하면 성공
- 없는 경우 None을 return 하기
⭐🌟 Follow up!
time complexity : O(n + m)
space complexity : O(1)
문제 자체는 쉬우니 follow up에 맞춰서 문제를 풀어보자.
space: O(n)
space: O(n) 전략을 찾아보려다가 도저히 떠오르지가 않아서, 일단 O(n)으로 해결가능하도록 문제를 풀었다.
time: O(m+n)은 맞췄다.
# 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
"""
# space: O(n)
a_set = set()
while headA != None:
a_set.add(headA)
headA = headA.next
while headB != None:
if headB in a_set:
return headB
headB = headB.next
return None
- 너무 단순하다.
- time complexity를 유지하면서도 space를 O(1)으로 만드는 방법이 도대체 무엇일까...
Space: O(1)
예제 입력을 아래와 같이 했을 때, 나오는 메세지이다.
intersectVal = 1
[1,2,3]
[3,2,1]
skipA = 0
skipB = 2
1 2 3
3 2 1
error message
The two lists should be the same starting from the intersection point.
겉으로 보기에는 문제가 없어 보이는데 왜 이런 메세지가 나오는 것일까.
- 몇개의 케이스를 추가하고 나서 보니 몇가지 특징을 알아냈다.
1. val값은 intersect 여부와 상관없다.
- skipA, skipB 값이 intersect 위치를 결정한다.
2. 반드시 같은 길이에서 시작해야한다.
121
123
차람 intersect위치로 부터 남은 list의 갯수가 서로 달라선 안된다.
👉 핵심은 같은 메모리 참조를 가지는 intersect의 시작점을 찾는 것이다.
🤔 결국 같은 길이에서 시작 할 수 밖에 없으니, 큰 길이를 미리 줄여도 되는 거 아닌가?
시도해보기
✅ 큰길이를 가진 LinkedList를 작은 길이에 맞춘다.
✅ 하나씩 탐색하면서, 같은 메모리를 참조하는지 확인한다.
>>> 메모리 참조 ?
# 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
"""
# space: O(1)
a_len = 0
b_len = 0
a_tmp = headA
b_tmp = headB
while a_tmp != None:
a_len += 1
a_tmp = a_tmp.next
while b_tmp != None:
b_len += 1
b_tmp = b_tmp.next
max_len = max(a_len, b_len)
dt = abs(a_len - b_len)
if max_len == a_len:
for i in range(dt):
headA = headA.next
else:
for i in range(dt):
headB = headB.next
has_intersection = False
while 1:
if headA == None and headB == None:
break
if headA == headB:
has_intersection = True
return headA
headA = headA.next
headB = headB.next
if not has_intersection:
return None
- 생각했던 방법이 정확히 맞았다!.
- 문제를 보기만 해서는 입력값의 패턴을 유추할 수 없었다.
- 직접 여러개 넣어보고 특징을 찾아냈음
- 속도: 125ms (88.73%) -> 114ms (98.97%)
- 공간: 42.70MB(13.11%) -> 42.42MB (33.44%)
- O(n) -> O(1)인데 생각보다 메모리 효율이 크게 증가하지 않는다.
🗝️ 좋은 관점
- 문제를 풀었으나 새로운 관점에서 두 노드의 intersetcion을 찾는 로직이 있어서 정리했다.
🗝️ 서로 다른 두 포인터가 하나는 nodeA에서 nodeB로, 하나는 nodeB에서 nodeA로 같은 속도로
순환한다면 intersection을 발견할 수 있다.
✅ ➕ = intersection 지점
[a1, a2, c1➕, c2, c3]
[b1, b2, b3, c1➕, c2, c3]
pointer 1 이동 경로
[a1, a2, c1➕, c2, c3, none, b1, b2, b3, c1➕, c2, c3, none]
pointer 2 이동 경로
[b1, b2, b3, c1➕, c2, c3, none, a1, a2, c1➕, c2, c3, none]
v
[a1, a2, c1➕, c2, c3, none, b1, b2, b3, c1➕, c2, c3, none]
v
[b1, b2, b3, c1➕, c2, c3, none, a1, a2, c1➕, c2, c3, none]
🏃♂️➡️ 같은 속도로 포인터가 이동되기 때문에 결국 뒤의 c1➕ 에서 만난다
❌ 겹침이 존재하지 않으면 결국 마지막 None에서 만난다.
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
dummy1, dummy2 = headA, headB
while dummy1!= dummy2:
dummy1 = dummy1.next if dummy1 else headB
dummy2 = dummy2.next if dummy2 else headA
return dummy1