Reverse k Elements
単一リンクリストと整数「k」が引数として渡されます。リストのk要素ずつ反転させるアルゴリズム体操。
k <= 1の場合、リストは変更されません。k >= n（nはリンクリストの長さ）の場合、リンクリスト全体を逆にします。
例
以下は、k = 3で、３要素ごとに反転した例です。
以下は、k = 4で、4要素ごとに反転した例です。
Solution
比較的に、単純な問題ですが、コード自体は、いくつかのポインターで追跡する必要があるため、少し複雑です。
このアルゴリズムにおいてのポイントは『２つの反転リストを使う』ことです。
一つ目は最終的に返り値として返す、全体反転リスト。
二つ目が全体反転リストに繋げていく、部分(k要素)反転リスト。
- reversed：全体反転リストの先頭を指すポインタ。返り値になります。
- current_head：サイズ「k」の部分反転リストの先頭。
- current_tail：サイズ 'k'の部分反転リストの末尾。
- prev_tail：既に処理された全体反転リストの末尾。
例えば、k = 5で、以下のリストがあるとします。
k要素ずつの部分反転リストを作って、全体反転リストに繋げていく感じになります。
実装
ReverseK.java
class ReverseK{
LinkedListNode reverse_k_nodes(LinkedListNode head, int k) {
if (k <= 1 || head == null) {
return head;
}
LinkedListNode reversed = null;
LinkedListNode prev_tail = null;
while (head != null & k > 0) {
LinkedListNode current_head = null;
LinkedListNode current_tail = head;
int n = k;
while (head != null && n > 0) {
LinkedListNode temp = head.next;
head.next = current_head;
current_head = head;
head = temp;
n--;
}
if (reversed == null) {
reversed = current_head;
}
if (prev_tail != null) {
prev_tail.next = current_head;
}
prev_tail = current_tail;
}
return reversed;
}
}