Algorithm

[바킹독의 실전 알고리즘 강의] 연결 리스트

연결 리스트 정리

 

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