この章について
連結リストに関する章です。
この章では単に"連結リスト"と書いてあるとき、双方向連結リストだと思うことにします。
連結リストとは
各ノードが前後のノードへのポインタを持ち、任意の位置への挿入・削除がO(1)で行える(はやい)コンテナクラス。
Question 2.1
ソートされていない連結リストから、重複する要素を削除するコードを書いてください。
発展問題
もし一時的なバッファが使用できないとすれば、どうやってこの問題を解きますか?
例 ： $L = 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\rightarrow 3\rightarrow 5$ に関数を適用 → $L = 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$
#include<list> //双方向リスト
#include<unordered_map>
#include<iostream>
using namespace std;
template<typename T>
void Unique1(list<T> &List){
unordered_map<T,bool> ap;
for(auto itr = List.begin();itr!=List.end();itr++){
if(ap[(*itr)]){List.erase(itr);}
else{ap[(*itr)] = 1;}
}
}
//発展問題の解答例
template<typename T>
void Unique2(list<T> &List){
for(auto itr = List.begin();itr!=List.end();itr++){
auto end = List.end();
for(auto itr2 = end;itr2!=itr;itr2--){
if((*itr)==(*itr2)){List.erase(itr2);}
}
}
}
Unique1 : 一度現れた値をunordered_mapに持ちながら走査する。時間計算量はO(N)。
Unique2 : 各要素ごとにlistの末尾から走査して、重複するなら削除する。時間計算量はO(N^2)。
Question 2.2
単方向連結リストにおいて、末尾から数えてk番目の要素を見つけるアルゴリズムを実装してください。
#include<forward_list> //単方向リスト
#include<iostream>
using namespace std;
template<typename T>
void k_th_element1(forward_list<T> &fList,int k){
auto itr = fList.begin();
int len = 0;
while(itr!=fList.end()){
itr++;
len++;
}
itr = fList.begin();
len-=k;
while(len){
itr++;
len--;
}
cout<<(*itr)<<endl;
}
template<typename T>
void k_th_element2(forward_list<T> &fList,int k){
auto itr = fList.begin();
auto itr2 = itr;
while(k){
itr2++;
k--;
}
while(itr2!=fList.end()){
itr++;
itr2++;
}
cout<<(*itr)<<endl;
}
k_th_element1 : (問題設定的に単方向リストの長さが与えられるわけがないので、)まずはリストの長さを取得しないといけない。
長さが分かれば後ろからk番目の要素は簡単に求められるので素直に実装した。
k_th_element2 : (想定解)ポインタを2つ用意する。どちらもforward_listの先頭のポインタで初期化しておく。片方を先にk進めておいて、その後2つのポインタを同時に進め、後ろのポインタが末尾に達したら推移をやめる。
このとき、手前のポインタは後ろからk番目の要素を指していることになる。
Question 2.3
単方向連結リストにおいて、間の要素(必ずしもちょうど中央というわけではなく、最初と最後の要素以外)で、その要素のみアクセス可能であるとします。その要素を削除するアルゴリズムを実装してください。
#include<forward_list> //単方向リスト
#include<iostream>
using namespace std;
template<typename T>
void erase_nth_element(forward_list<T> &fList,int n){
auto it1 = fList.begin();
int len = 0;
//it1がn番目の要素を指すようにセット
while(n!=1){
it1++;
n--;
len++;
}
//it2がn番目、it1がn+1番目を指すようにセット
auto it2 = it1;
it1++;
//n番目の要素を消したいので順に次の要素に上書きしていく。
while(it1!=fList.end()){
(*it2) = (*it1);
it2++;
it1++;
len++;
}
//リストの長さが変わってないため最後の要素を消すためにresize
fList.resize(len);
}
なんかうまくiteratorを引数にできなかったのでn番目の要素を削除するコードにした。(とても微妙)
Question 2.4
ある数xが与えられたとき、連結リストの要素を並び替え、xよりも小さいものが前にくるようにするコードを書いてください。xがリストに含まれる場合、xの値はxより小さい要素の後にある必要があります(例を参照してください)。区切り要素のxは右半分のどこに現れてもかまいません。左半分と右半分のちょうど間にある必要はないということです。
例
入力 : $3 \rightarrow 5 \rightarrow 8 \rightarrow 5 \rightarrow 10 \rightarrow 2 \rightarrow 1$ [区切り要素=5]
出力 : $3 \rightarrow 1 \rightarrow 2 \rightarrow 10 \rightarrow 5 \rightarrow 5 \rightarrow 8$
#include<list> //双方向リスト
#include<iostream>
using namespace std;
void func(list<int> &List,int x){
for(auto it = List.begin();it!=List.end();it++){
if((*it) < x){
List.push_front((*it));
List.erase(it);
}
}
}
問題文の解釈が合ってるか自身がない...もし正しい解釈知ってる方いたら教えてください...
とりあえず自分は「xより小さい数をxより左に持ってくればオーケー」という風に解釈しました。
指定された数xに対してリストを走査して、xより小さい要素を見つけたら先頭に持ってきて元の位置からは削除、という風にやればxより小さい数はxより左にしか並ばないことになる。
Question 2.5
各ノードの要素が1桁の数である連結リストで表された2つの数があります。一の位がリストの先頭になるように、各位の数は逆順に並んでいます。このとき2つの数の和を求め、それを連結リストで表したものを返す関数を書いてください。
例
入力 : $7 \rightarrow 1 \rightarrow 6 + 5 \rightarrow 9 \rightarrow 2：(617 + 295を表す)$
出力 : $2 \rightarrow 1 \rightarrow 9 ：(912を表す)$
#include<list> //双方向リスト
#include<iostream>
using namespace std;
//筋の悪い解法
list<int> addition(list<int> &num1,list<int> &num2){
list<int> ans;
int n1=0,n2=0,ord1=1,ord2=1;//ord1,ord2のオーバーフローに注意
for(auto it = num1.begin();it!=num1.end();it++){
n1+=ord1*(*it);
ord1*=10;
}
for(auto it = num2.begin();it!=num2.end();it++){
n2+=ord2*(*it);
ord2*=10;
}
int n = n1 + n2;
while(n){
ans.push_back(n%10);
n/=10;
}
return ans;
}
//マシな方の解法
list<int> addition2(list<int> &num1,list<int> &num2){
list<int> ans;
auto it1 = num1.begin(), it2 = num2.begin();
/*
桁数が違う時に下のwhile文での実装がうまくいかなかったので短い方のlistをresizeして足りない部分を0埋めした
C++11以降だとlist.size()が定数時間らしいので甘えた
*/
int s1 = num1.size(), s2 = num2.size();
if(s1>s2){num2.resize(s1);}
else{num1.resize(s2);}
int next = 0, r = 0; //nextが繰り上がる数、rが位の数
while(it1!=num1.end()&&it2!=num2.end()){
if(it1==num1.end()){
r = next + (*it2);
it2++;
}
else if(it2==num2.end()){
r = next + (*it1);
it1++;
}
else{
r = next + (*it1) + (*it2);
it1++;it2++;
}
next = r/10;
r %= 10;
ans.push_back(r);
}
//最後の繰り上がりが残る可能性を考慮するとこの1行が必要になる
if(next){ans.push_back(next);}
return ans;
}
addition1 : 数が桁ごとに与えられたときのありがちな構成。これだと小さい桁数ですぐオーバーフローするのであまり賢くない。
addition2 : マシな解法。これは繰り上がりをコツコツ計算してるのでオーバーフローも起きないし、任意の桁数に対応できるので多倍長整数とか考えなくていいなあと思った(小並感)
Question 2.6
連結リストが回文(先頭から巡回しても末尾から巡回しても、各ノードの要素がまったく同じになっている)かどうかを調べる関数を実装してください。
#include<list> //双方向リスト
#include<iostream>
using namespace std;
template<typename T>
bool palindrome1(list<T> &List){
auto bgn = List.begin(), end = List.end();
end--; //List.end()の指す場所だけ注意
while(1){
if(bgn==List.end()){return true;}
else if((*bgn)!=(*end)){return false;}
bgn++;
end--;
}
return true;
}
template<typename T>
bool palindrome2(list<T> &List){
list<T> rList = List;
rList.reverse();
return List==rList;
}
1章で似たようなのをやった気がするので割愛。両側から見ましょう。
もちろん真ん中まで比べれば十分だが書くのが面倒だった(完)
Question7と8はうまく書けなかったので方針だけということに...(ゆるして)
Question 2.7
2つの(単方向)連結リストが与えられるとき、2つのリストが共通かどうかを判定してください。また、共通するノードを返してください。共通するというのは、そのノードの参照が一致するかであって値が一致するかどうかではないという点に注意してください。つまり、1つ目の連結リストのk番目のノードが、2つ目の連結リストのj番目のノードが完全に(参照によって)一致する場合、共通するといえます。
要は2つの連結リスト$L_1, L_2$に対してあるノード$N_1,N_2$が存在して、(ノードとして)$N_1 = N_2$になっていれば、そのノードから2つのリストが合流するのでそれを探す。
例えば、
$L_1 = 3\rightarrow 1\rightarrow 5\rightarrow 9\rightarrow$ 7 $\rightarrow 2\rightarrow 1,$
$L_2 = 4\rightarrow 6\rightarrow $ 7 $\rightarrow 2\rightarrow 1$
とし、赤い7への参照が完全に一致したとする。このとき、図としては以下のようになっている。
$L_1 = 3\rightarrow 1\rightarrow 5\rightarrow 9$
$↘$
$7\rightarrow 2\rightarrow 1$
$↗$
$L_2 = 4\rightarrow 6$
図から分かるように、この場合だと$L_1$の先頭2つの要素は不要そうなので、$L_1$と$L_2$の長さを揃えてから調べて、それぞれの先頭のポインタを同時に進めながら比較するとよい。一致したら終わり、末尾まで進めても一致しなかったら共通部分なし。
〜途中で一瞬困ったこと〜
$L_1$と$L_2$が以下のようになってたらどうしようと思った。(合流した後に途中で$L_1$だけ切れる場合)
$L_1 = 3\rightarrow 1\rightarrow 5\rightarrow 9$
$↘$
$7\rightarrow$ $2$
$↗$ $↘$
$L_2 = 4\rightarrow 6$ $1$
が、そうなると赤字の2のノードが参照するものが、$L_1$から見るとNULL、$L_2$から見ると次の1のノード、ということになってまずいことに気づいたのでこういう場合は考えなくて大丈夫だという結論になった。
(2020/5/6追加)こっちもちゃんと実装しました。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isCommon(ListNode *p,ListNode *q){
if(!p||!q){return true;}
ListNode *phead = p;
ListNode *qhead = q;
int m = 0, n = 0;
while(phead){
phead = phead->next;
m++;
}
while(qhead){
qhead = qhead->next;
n++;
}
if(m>n){
swap(m,n);
swap(p,q);
}
int r = n - m;
while(r){
r--;
q = q->next;
}
return (p==q);
}
Question 2.8
循環する連結リストが与えられたとき、循環する部分の最初のノードを返すアルゴリズムを実装してください。
定義
循環を含む連結リスト : 連結リストAではループを作るために、リスト内のノードの次へのポインタが以前に出現したノードを指している。
例
入力 : A -> B -> C -> D -> E -> C [最初のCと同じもの]
出力 : C
与えられる連結リストに末尾がないので、2つのポインタを用意して片方を末尾まで進めて、もう片方は末尾と一致するまで先頭からポインタを進める・・・という方法が取れない。
そこで、走査する速さが異なる2つのポインタ(fast, slow)を用意する。slowは1つずつ進めて、fastは2つずつ進める。
そうすれば、2つともループに入った後にいつか必ず重なる瞬間が存在する。
しかし、以下の例のように重なった瞬間のノードが答えのノードかというと、そうではないことがある。
$L = 5\rightarrow 2 \rightarrow 7\rightarrow$ $ 1 $ $\rightarrow
8$
$\uparrow$ $\downarrow$
$6 \leftarrow 2$
この例だとfastとslowが最初に出会うのは8のノードになる。この差を解消しなければならない。
結論としては、ループしている部分の長さを$K$、ループの外の部分の長さを$r$としたとき、ループの始点(赤いノード)から$K-r (mod K)$だけ進んだところにある。
なぜなら、slowがループの始点に入った時、ポインタの進め方から、fastはslowより$r$だけ進んだ所にいる。
その状態から再び動き始めて次に重なるまで、slowが$K-r$進んだ時にfastは$2K-2r$進んでいて、もともとslowより$r$進んでいたことを考慮すると、ループ内の剰余は$2K-2r+r=2K-r≡K-r(mod K)$となり、slowの進んだノード数の剰余と等しくなるので、重なっている。
この方法を取ることで、同時にループの長さとループ外の部分の長さも得られているので、必要な分だけ好きな方のポインタを進めることで、ループの始点のノードを返すことができる。
(2020/5/6追加)
忘れてたので実装しました。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool hasCycle(ListNode *head) {
if(head==NULL || head->next==NULL){return false;}
ListNode *slow = head;
ListNode *fast = head->next;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast){return true;}
}
return false;
}