연결 리스트 정리
2021.03.07 - [Computer Science/DataStructure] - Linked List (연결 리스트)
연결 리스트 문제
손코딩 문제 1
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?
정답
동일한 노드가 나올 때 까지 계속 다음 노드로 가면 됨
공간복잡도 O(1), 시간복잡도 O(N)
손코딩 문제 2
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법?
정답
일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함.
그 후 다시 두 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고,
두 시작점이 만날 때 까지 두 시작점을 동시에 한 칸씩 전진시키면 됨.
공간복잡도 O(1), 시간복잡도 O(A+B)
손코딩 문제 3
주어진 연결 리스트 안에 사이클이 있는지 판단하라
정답
Floyd's cycle-finding algorithm
공간복잡도 O(1), 시간복잡도 O(N)
Floyd's cycle-finding algorithm (이하 설명은 chatGpt를 활용했습니다.)
Floyd's cycle-finding algorithm은 링크드 리스트나 배열과 같은 자료 구조에서 순환 구조를 찾는 알고리즘이다.
이 알고리즘은 2개의 포인터를 사용하여 구현되는데,
한 포인터는 한 번에 한 칸씩 이동하고 다른 포인터는 한 번에 두 칸씩 이동한다.
이 두 포인터는 시작점에서 출발하여 두 포인터가 만날 때까지 계속해서 이동한다.
이 알고리즘의 핵심 아이디어는 두 포인터가 만날 때까지 두 포인터가 지나간 노드의 개수가 서로 다르다는 것이다. 만약 순환 구조가 있다면, 두 포인터는 언젠가는 순환 구조에서 만날 것이고,
두 포인터가 만날 때까지 이동한 거리의 차이는 순환 구조 내의 노드 개수와 같아진다.
만약 순환 구조가 없다면, 두 포인터는 리스트의 끝에서 만나게 된다.
따라서, 두 포인터가 만날 때까지 이동한 거리의 차이를 이용하여 순환 구조의 시작점을 찾을 수 있다.
이 알고리즘은 시간 복잡도가 O(n)으로 매우 빠르며, 상수항이 작아 실제로도 많이 사용되는 알고리즘이다.
아래는 Floyd's cycle-finding algorithm의 구현 예시이다.
python
def findCycleStart(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not fast or not fast.next:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
java
public class CycleFinder {
public static ListNode findCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// cycle found, reset slow pointer to head
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
// no cycle found
return null;
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = head.next.next; // cycle
ListNode cycleStart = findCycle(head);
System.out.println(cycleStart.val); // output: 3
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
References By
https://www.youtube.com/watch?v=C6MX5u7r72E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=5
'Algorithm' 카테고리의 다른 글
[바킹독의 실전 알고리즘 강의] 스택의 활용 (수식의 괄호 쌍) (0) | 2023.07.04 |
---|---|
[바킹독의 실전 알고리즘 강의] 덱 (0) | 2023.05.25 |
[바킹독의 실전 알고리즘 강의] 큐 (0) | 2023.05.09 |
[바킹독의 실전 알고리즘 강의] 스택 (0) | 2023.05.03 |
[바킹독의 실전 알고리즘 강의] 배열 (0) | 2023.04.17 |