[코딩인터뷰 완전정복] 2.8 루프 발견

Q : 순환 연결리스트(circular linked list)가 주어졌을 때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다.

// LinkedList.h

#include <iostream>

template <class T>

struct node {

    T data;

    node *next;

};

template <class T>

class linked_list{

private:

    node<T> *head, *tail;

public:

    linked_list() {

        head = NULL;

        tail = NULL;

    }

    node<T>* add_node(T n) {

        node<T> *temp = new node<T>;

        temp->data = n;

        temp->next = NULL;

        if (head == NULL) {

            head = temp;

            tail = temp;

        }

        else {

            tail->next = temp;

            tail = tail->next;

        }

        return temp;

    }

    void addFirst(T x) {

        node<T> *temp = new node<T>;

        temp->data = x;

        temp->next = head;

        head = temp;

        if (tail == NULL) tail = temp;

    }

    void addFirst(node<T> *node) {

        node->next = head;

        head = node;

        if (tail == NULL) tail = node;

    }

    int removeFirst() {

        if(head == NULL) return NULL;

        int data = head->data;

        head = head->next;

        return data;

    }

    node<T>* first() {

        return head;

    }

    void printLinkedList() {

        if (head == NULL) return;

        node* currentNode = head;

        while (currentNode->next != NULL) {

            printf("%d - ", currentNode->data);

            currentNode = currentNode->next;

        }

        printf("%d", currentNode->data);

        printf("\n");

    }

};

 

#include <iostream>

#include <unordered_set>

#include "LinkedList.h"

template <class T>

node<T>* FindLoop(linked_list<T> list) {

    node<T> *itr = list.first();

    std::unordered_set<node<T>*> set;

    while (1) {

        if (set.find(itr) != set.end()) return itr;

        set.insert(itr);

        itr = itr->next;

        if (itr == NULL) return NULL;

    }

}

int main() {

    linked_list<int> list;

    list.add_node(1);

    node<int> *looped = list.add_node(2);

    list.add_node(3);

    list.add_node(4);

    list.add_node(1);

    list.add_node(2);

    node<int> *looping = list.add_node(3);

    looping->next = looped;

    node<int> *loopNode = FindLoop(list);

    if (loopNode == NULL) printf("No Loop\n");

    else printf("%d\n", loopNode->data);

}

 

연결리스트에 속해있는 Node의 주소를 hash set에 담는다.

이터레이터가 NULL을 가리키면 리스트가 순환하지 않는다는 뜻이다.

hash set에 이미 등록된 주소가 나오면 그 주소를 리턴한다.

시간복잡도 O(N) 공간복잡도 O(N)

 

 

* 다른 방법

리스트를 손상시켜도 된다면 연결리스트의 tail부터 순회하며 next가 NULL이 될 때 까지 next를 NULL로 바꿔버린다.

그렇게 하면 순환되는 첫번째 노드가 연결리스트의 마지막에 오게 된다.

시간복잡도 O(N) 공간복잡도 O(1)