リストのつなぎかえ
リストは一本の紐のようにつながっている。これを、途中で切り分けてつなぎ変え、かたまり（セグメント）の順番を変えることが配列より高速にできる。
たとえば head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 ->NULL というリストを 1から5と6から9の前後半の二つに分け、入れ替えて、head -> 6 -> 7 -> 8 -> 9 -> 1 -> 2 -> 3 -> 4 -> 5 ->NULL と変更することができる。
出来上がりを前からみて、変更点をまとめると
9- > 1 につなぎ替え
head -> 6 につなぎ替え
5 -> NULL につなぎ替え
以上の３つが行われていることが分かる。
部分的なプログラムで書くと listchange1.c のようになる。node_search()はリストの削除で定義している。 code:listchange1.c
Node *head, *f, *r, *w;
//
f = node_search(head, 5); // 4のノードを指している f->next は5のノードを指している
r = node_search(head, 9); // 8のノードを指している
f = f->next; // fが5のノードを指すことになる
r = r->next; // rが9のノードを指す
r->next = head->next;
head->next = f->next;
f->next = NULL;
クイズ
つなぎ替えの様子を図に書いてみよう
演習
1) 1から10の数字をリストとして持って、一度表示してから、5と6で区切って半分ずつ前後交換するプログラムを書こう。リストの削除のプログラムを参考にしよう。