背景
コーディングインタビューの練習問題として、
連結リストのサイクル検出問題を解いたので、
その解法をメモしておく。
目次
連結リストとは
連結リストは、各要素が一つ前あるいは後ろの要素へのリンクを持つ
リストである。そのため、同じ要素数を持つ配列よりも多くのメモリを
消費する。
ただし、要素を挿入あるい削除するとき、配列では後ろの要素を全て
ずらす必要があるのに対して、連結リストはその箇所のリンクを繋ぎ
変えるだけになるので、計算時間が短くなる。
サイクル検出
連結リストのサイクルとは、下図のようにリストのノードを
辿っていくと、再び既存のノードと連結しループする状態の
ことである。
ある連結リストに対して、それがサイクルしているか、あるいは
どのノードからサイクルは始まっているかを検出するのが 、
サイクル検出問題である。
解法
今回はハッシュテーブルを利用した解法についてまとめる。
ハッシュテーブルについてはこちらの記事を参照。
qiita.com
zenn.dev
与えられた連結リストのノードを順に辿っていき、
それがハッシュテーブルに既に記録されているかを
チェックする。もし見つかれば、それはまた同じノードに
戻ってきたことになり、サイクルしていると判定する。
逆にテーブル内に見つからなければ、それは初めて訪れたノード
として、ハッシュテーブルに新たに記録する。
以上の処理を行うC++コードは下記のようになる。
#include <iostream> #include <string> #include <unordered_set> using namespace std; // linked list node struct Node { int data; struct Node *next; }; // add new data void push(struct Node **head, int new_data) { // allocate node struct Node *new_node = new Node; // put in the data new_node->data = new_data; // link the old list off the new node new_node->next = (*head); // move the head to pointer to the new node (*head) = new_node; } // return true if there is a cycle in linked list bool detect_cycle(struct Node *head) { unordered_set<Node *> nodes; while (head != NULL) { // this node is already present if (nodes.find(head) != nodes.end()) return true; // see the node for the first time nodes.insert(head); head = head->next; } return false; } // main process int main(void) { // start with the empty list struct Node *head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); // create a cycle head->next->next->next->next = head; if (detect_cycle(head)) cout << "Cycle found" << endl; else cout << "No cycle" << endl; return 0; }
このコードでは、与えられた連結リストに対して
サイクル検出の処理を行い、サイクルしていれば
True、そうでなければFalseを返すようにしている。
また、もう一つのパターンとして、サイクルの開始点である
ノードのポインタを返す問題もある。その場合のサイクル
検出部分のコードは下記のようになる。
Node *detect_cycle(struct Node *head) { unordered_set<Node *> nodes; Node *node = head; while (head != NULL) { // this node is already present if (nodes.find(head) != nodes.end()) return node; // see the node for the first time nodes.insert(head); head = head->next; } return NULL; }
