背景

プログラミングテストの練習問題として、
重複したノードを含んだ連結リストをユニークに
する問題を解いたので、その解法をメモしておく。

連結リストに関する類題

これまでに解いた連結リスト関連の問題はこちらを参照。

問題

下図の上部にあるような連結リストが入力として与えられたとき、
そこから重複したノードを削除し、下図の下部のようなユニークな
ノードで構成される連結リストにするアルゴリズムを実装する。
f:id:sy4310:20220313110721p:plain

他にもこういうパターンもある。
f:id:sy4310:20220313110820p:plain

解法

入力された連結リストの各ノードが持つ数値と、その次に来るノードの
数値を比較する。それらが一致していれば、次に来ていたノードの
ポイントを、そのまた次に来るノードのポインタと入れ替える。
この一連の処理を、参照するノードのポインタがNULLになるまで
繰り返す。

以上のアルゴリズムを実装した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;
}

// delete duplicated nodes
Node* delete_duplicates(Node* head) {
  Node* current = head;

  while (current != NULL && current->next != NULL) {
    if (current->next->data == current->data) {
      current->next = current->next->next;
    }
    else {
      current = current->next;
    }
  }

  return head;
}

// main process
int main(void) {
  // start with the empty list
  Node* head = NULL;

  // create sorted linked list
  // sorted in ascending order
  push(&head, 1);
  push(&head, 1);
  push(&head, 1);
  push(&head, 2);
  push(&head, 2);
  push(&head, 3);
  push(&head, 3);
  push(&head, 3);

  Node* result = NULL;
  result = delete_duplicates(head);

  // print data of each node
  Node* current = result; 
  while (current != NULL)
  {
    cout << current->data << endl;
    current = current->next;
  }
  
  return 0;
}

このアルゴリズムでは、ノードをリストの先頭からノードの
数分だけ順番に参照していくだけなので、計算時間はO(n)になる。

EurekaMoments

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

重複したノードを含んだ連結リストをユニークなリストにする問題とC++サンプルコード

背景

目次

連結リストに関する類題

問題

解法