作者:米田優峻
技術評論社

背景

プログラミングテストの練習問題として、
連結リストから重複したノードを全て削除
する問題を解いたので、その解法をメモ
しておく。

連結リストに関する類題

これまでに解いた連結リストに関する問題はこちら。

問題

下図のように、重複したノードを含みつつ昇順にソートされた連結リストが
入力されたとして、その中から重複したノードを全て削除するアルゴリズムを
考える。
この時に期待される出力は、もともと1個ずつしかないノードのみが残った
連結リストである。

解法

削除されるべきはこのようなリストである。
f:id:sy4310:20220313122326p:plain

この問題を解くために、ここではSentinel nodeとPredecessorという
二つの概念を活用する。

en.wikipedia.org

Sentinel nodeとは、データを持たない疑似的なノードである。
今回のような問題の場合、入力された連結リストの先頭や最後尾の
ノードが削除される場合があり、そうなるとうまくリストを辿ることが
出来なくなる。
そのため、疑似的なノードをそれらの前後に加えることにより、
入力リストの端のノードも処理できるようにしている。
f:id:sy4310:20220313122703p:plain

また、Predecessorとは、今回の問題で削除されるノードの一つ前の
ノードの呼び方である。削除対象となる重複ノードを見つけたら、
その前にあるPredecessorの次に来るノードのポインタに、削除される
ノードリストの後にくるノードのポインタを付け替えることで、
重複ノードの削除を実現する。

このアルゴリズムをC++で実装すると下記のようになる。

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

// linked list node
struct Node {
  int data;
  Node *next;
  Node() : data(0), next(NULL) {}
  Node(int x, Node* next) : data(x), next(next) {}
};

// add new data
void push(struct Node **head, int new_data) {
  // allocate node
  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) {
  // sentinel
  Node* sentinel = new Node(0, head);

  // predecessor = the last node
  // before the sublist of duplicates
  Node* pred = sentinel;

  while (head != NULL) {
    // if it's beginning of duplicates sublist
    // skip all duplicates
    if (head->next != NULL && head->data == head->next->data) {
      // move till the end of duplicates sublist
      while (head->next != NULL && head->data == head->next->data) {
        head = head->next;
      }
      // skip all duplicates
      pred->next = head->next;
    }
    else { // otherwise, move predecessor
      pred = pred->next;
    }
    
    // move forward
    head = head->next;
  }

  return sentinel->next;
}

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

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

  Node* result = delete_duplicates(head);

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