(알고리즘 문제) 두 연결리스트에서 노드의 교집합 찾기
두 연결리스트에서 노드의 교집합 찾기 코딩인터뷰 완전분석 - 게일 라크만 맥도웰
교집합: 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노트를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 천 번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.
단방향 알고리즘의 특성상 같은 노드를 바라보게 되면 그 이후로는 데이터가 같다. 따라서 뒤에서부터 길이를 일치시키면 되겠다.
예를 들어
a : 1 - 2 - 3 - 4 - 7 - 8 - 9
b : 5 - 6 - 7 - 8 - 9
라는 두 단방향 연결리스트가 있다면
둘이 같은 노드를 바라보는 7 부터는 동일하게 된다.
따라서 뒤에서 부터
| a | 1 | 2 | 3 | 4 | 7 | 8 | 9 |
| b | 5 | 6 | 7 | 8 | 9 |
이렇게 길이를 맞춰준다고 봤을 때
a의 1, 2 를 생략하고
a의 3, b의 5 부터 비교를 해나가면
a의 7, b의 7 에서 동일한 부분이 나오게 된다.
이 것을 코드로 작성을 해보면 다음과 같다.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_intersection(a, b):
length_a = get_length(a)
length_b = get_length(b)
if length_a > length_b:
for _ in range(length_a - length_b):
a = a.next
elif length_a < length_b:
for _ in range(length_b - length_a):
b = b.next
# a와 b의 길이가 같게 되었기 때문에 a 만 체크하였다.
while a:
if a is b:
return a
a = a.next
b = b.next
return None
def get_length(head):
length = 0
current = head
while current:
length += 1
current = current.next
return length
intersection = Node(7, Node(8, Node(9)))
a = Node(1, Node(2, Node(3, Node(4, intersection))))
b = Node(5, Node(6, intersection))
result = find_intersection(a, b)
while result:
print(result.val, end=" -> ")
result = result.next
print("None")
python ref id 얻기
id(object)
Return the “identity” of an object. This is an integer which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value.
동일한 lifetime 내에서 id가 같으면 같은 객체이다.
출처
파이썬 is 와 == 의 차이
is 연산자는 두 객체가 동일한 객체인지를 비교합니다. 즉, 두 객체의 메모리 주소가 동일한지를 확인합니다.
== 연산자는 두 값이 동등한지를 비교합니다.