Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@yutakihara

アルゴリズム 体操18

More than 1 year has passed since last update.

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;
  }
}
0
Help us understand the problem. What is going on with this article?
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.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?