2021년 3월 LeetCoding Challenge — 4일차: 두 연결 목록의 교차점

2021년 3월 리트코딩 챌린지 4번째 문제를 풀어보겠습니다.

문제 설명

두 단일 연결 리스트의 교차점이 시작되는 노드를 찾는 프로그램을 작성하세요.

예를 들어, 다음 두 개의 연결된 목록은 다음과 같습니다.



노드 c1에서 교차하기 시작합니다.

예 1:

**Input: **intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
**Output:** Reference of the node with value = 8
**Input Explanation:** The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

예 2:

**Input: **intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
**Output:** Reference of the node with value = 2
**Input Explanation:** The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

예 3:

**Input: **intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
**Output:** null
**Input Explanation:** From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
**Explanation:** The two lists do not intersect, so return null.

메모:

두 개의 연결된 목록에 교차가 전혀 없으면 null을 반환합니다.

연결된 목록은 함수가 반환된 후에도 원래 구조를 유지해야 합니다.

연결된 전체 구조의 어디에도 순환이 없다고 가정할 수 있습니다.

각 연결 목록의 각 값은 [1, 10^9] 범위에 있습니다.

코드는 가급적 O(n) 시간에 실행하고 O(1) 메모리만 사용해야 합니다.

해결책

이 문제는 여러 가지 방법으로 해결할 수 있습니다. 여기서 우리는 두 가지 접근법에 대해 논의할 것입니다.

접근법 1 - HashSet 사용: 여기서는 두 Linked List 사이의 교차점을 찾습니다. 따라서 교차점은 연결된 목록 모두에서 공통입니다. 따라서 HashSet을 사용하여 이 문제를 해결할 수 있습니다. 이 접근 방식을 사용하면 첫 번째 연결 목록의 노드를 HashSet에 저장합니다. 그런 다음 두 번째 Linked List를 순회하고 HashSet에서 이전에 해당 노드를 만났는지 확인합니다. HashSet에 있는 첫 번째 노드와 두 번째 목록을 찾으면 반환합니다.

m과 n이 각각 첫 번째와 두 번째 Linked List의 크기이면

시간 복잡도: O(m+n)

공간 복잡도:O(m)

접근법 2 — 상수 공간: 이 접근 방식을 사용하면 연결 목록을 모두 탐색하고 headA를 가리키는 tempA와 headB를 가리키는 tempB를 가져옵니다. Linked List는 길이가 다르기 때문에 이를 고려해야 합니다. 첫 번째 목록의 끝에 도달할 때마다 tempA를 두 번째 목록의 시작으로 설정하고 그 반대도 마찬가지입니다. 그런 식으로 두 목록을 순회하면 동일한 길이를 순회하는 포인터를 얻을 수 있습니다. 우리는 tempA==tempB를 찾을 때까지 루프를 실행합니다. 자세한 설명은 Leetcode 솔루션 페이지에서 찾을 수 있습니다.

시간복잡도 : O(m+n)

공간 복잡도: O(1)

여기에서도 코드를 찾을 수 있습니다.

3월 리트코딩 챌린지의 이전 문제도 올렸습니다. 내 프로필에서 확인하세요.