C++で2つの連結リストの交点を見つける方法

連結リストとは

連結リスト(Linked List)は線形データ構造の一種です。各ノードは2つの部分で構成されており、一方にはノードの値(データ)が、もう一方には次のノードへのアドレス(ポインタ)が格納されています。

ここでは、各ノードがリスト内の他のノードを指すポインタを持つ連結リストを想定します。この問題のタスクは、2つの連結リストが交差するノードを見つけることです。交差していない場合は、NULL(空)を出力として返します。

入力例1

出力:

2

解説: 与えられた連結リストは値「2」のノードで交差しているため、「2」を出力として返します。

入力例2

出力:

NULL

解説: 共通するノードが存在しないため、この場合はNULLを返します。

この問題を解くためのアプローチ

2つの連結リストには、互いに交差する共通のポイントがあります。交点を見つけるには、両方の連結リストを走査し、同じノードを指している位置を特定します。ある時点で次のノードへのポインタが一致するため、その時点のノードの値を返せばよいのです。

• データと次のノードへのポインタを持つ2つの連結リストを用意します。
• 関数 commonPoint(listnode* headA, listnode* headB) は、2つの連結リストの先頭ポインタをそれぞれ受け取り、共通の交点となるノードの値を返します。
• 連結リストの長さを求める整数型の関数を作成し、各リストの先頭から長さを返します。
• 両方のリストの先頭へのポインタを作成し、長い方のリストを(最初のリストの長さ − 2番目のリストの長さ)分だけ先に進めます。
• その後、次のポインタが等しくなるまで両方のリストを同時に走査します。
• 両方のリストが交差するノードの値を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class listnode {
    public:
        int data;
    listnode * next;
};
// 連結リストの長さを求める関数
int count(listnode * head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head -> next;
    }
    return count;
}
// 2つの連結リストの共通点を取得する関数
int commonPoint(listnode * headA, listnode * headB) {
    int len1 = count(headA);
    int len2 = count(headB);
    listnode * p1 = headA;
    listnode * p2 = headB;
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; ++i) {
            p1 = p1 -> next;
        }
    }
    if (len1 < len2) {
        for (int i = 0; i < len2 - len1; ++i) {
            p2 = p2 -> next;
        }
    }
    while (p1 != NULL and p2 != NULL) {
        if (p1 == p2) {
            return p1 -> data;
        }
        p1 = p1 -> next;
        p2 = p2 -> next;
    }
    return -1;
}
int main() {
    listnode * head;
    listnode * headA = new listnode();
    headA -> data = 5;
    listnode * headB = new listnode();
    headB -> data = 4;
    head = new listnode();
    head -> data = 9;
    headB -> next = head;
    head = new listnode();
    head -> data = 2;
    headB -> next -> next = head;
    head = new listnode();
    head -> data = 7;
    headA -> next = head;
    headB -> next -> next -> next = head;
    head = new listnode();
    head -> data = 3;
    headA -> next -> next = head;
    headA -> next -> next -> next = NULL;
    cout << commonPoint(headA, headB) << endl;
}

上記のコードを実行すると、以下の出力が得られます。

出力

7

解説: 与えられた2つの連結リストは、値「7」のノードで合流しています。長い方のリストのポインタを先に進めて開始位置を揃えることで、以降は同じステップで比較でき、交点を効率的に検出できます。