Help us understand the problem. What is going on with this article?

アルゴリズム 体操18

Reverse k Elements

単一リンクリストと整数「k」が引数として渡されます。リストのk要素ずつ反転させるアルゴリズム体操。
k <= 1の場合、リストは変更されません。k >= n(nはリンクリストの長さ)の場合、リンクリスト全体を逆にします。

以下は、k = 3で、3要素ごとに反転した例です。
Screen Shot 2020-01-23 at 9.51.00.png
以下は、k = 4で、4要素ごとに反転した例です。
Screen Shot 2020-01-23 at 9.51.40.png

Solution

比較的に、単純な問題ですが、コード自体は、いくつかのポインターで追跡する必要があるため、少し複雑です。
このアルゴリズムにおいてのポイントは『2つの反転リストを使う』ことです。
一つ目は最終的に返り値として返す、全体反転リスト。
二つ目が全体反転リストに繋げていく、部分(k要素)反転リスト。

  1. reversed:全体反転リストの先頭を指すポインタ。返り値になります。
  2. current_head:サイズ「k」の部分反転リストの先頭。
  3. current_tail:サイズ 'k'の部分反転リストの末尾。
  4. prev_tail:既に処理された全体反転リストの末尾。

例えば、k = 5で、以下のリストがあるとします。
Screen Shot 2020-01-23 at 10.01.14.png

k要素ずつの部分反転リストを作って、全体反転リストに繋げていく感じになります。
Screen Shot 2020-01-23 at 10.02.12.png
Screen Shot 2020-01-23 at 10.06.26.png

実装

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;
  }
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした