EurekaMoments

ロボットや自動車の自律移動に関する知識や技術、プログラミング、ソフトウェア開発について勉強したことをメモするブログ

連結リストのサイクル検出問題とC++サンプルコード

背景

コーディングインタビューの練習問題として、
連結リストのサイクル検出問題を解いたので、
その解法をメモしておく。

目次

連結リストとは

連結リストは、各要素が一つ前あるいは後ろの要素へのリンクを持つ
リストである。そのため、同じ要素数を持つ配列よりも多くのメモリを
消費する。
ただし、要素を挿入あるい削除するとき、配列では後ろの要素を全て
ずらす必要があるのに対して、連結リストはその箇所のリンクを繋ぎ
変えるだけになるので、計算時間が短くなる。

サイクル検出

連結リストのサイクルとは、下図のようにリストのノードを
辿っていくと、再び既存のノードと連結しループする状態の
ことである。
f:id:sy4310:20220228222424p:plain
ある連結リストに対して、それがサイクルしているか、あるいは
どのノードからサイクルは始まっているかを検出するのが 、
サイクル検出問題である。

解法

今回はハッシュテーブルを利用した解法についてまとめる。
ハッシュテーブルについてはこちらの記事を参照。
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;
}