アルゴリズム 体操17

Rotate a Linked List

説明

単一リンクリストのヘッドノードと整数 nを指定すると、リンクリストを n回転させるアルゴリズム体操。

以下、2つの例があります。引数として渡されたリンクリストと整数 n = 2回転後の出力です。

n の値は、リンクリストの長さよりも大きくなる可能性があることに注意してください。

n = -2の時、

Solution

Runtime Complexity O(n)

n は　リンクリストの長さです。

Memory Complexity O(1)

新しくデータ構造を使う必要はありません。ポインタのみ。

1. まず、リンクリストの長さを見つけます。
2. nが負の場合、またはnがリンクリストの長さよりも大きい場合、リンクリストの末尾で必要な回転数に合わせて調整します。 調整された数値は常に整数 N です（0 <= N <n）。調整された回転数が0の場合、ヘッドポインターを返すだけです。これは、回転が必要なかったことを意味します。
3. リンクリストの最後のノードからn番目の 'x' ノードを見つけます。基本的に長さ「n-N」でノードxに到達します。このノードの前のノードの次のポインターは リストの末尾のノードになるため、NULLを指すように更新する必要があります。
4. x から、リンクリストの最後のノードに移動します。最後のノードの次のポインターを、ヘッドノードに更新させます。
5. 新しいヘッドノードとして new_head を作成します。 new_head は、n回の回転を実行した後のリンクリストの先頭になります。

『百聞は一見にしかず』ということで、上のアルゴリズムでn = 2の上記のリンクリストを回転させてみましょう。

実装

RotateList.java

class RotateList{

  private int getListSize(LinkedListNode head) {
    LinkedListNode curr = head;
    int listSize = 0;

    while (curr != null) {
       listSize++;
       curr = curr.next;
     }
     return listSize;
  }

  private int adjustRotatationsNeeded(int n, int length) {
    return n < 0 ? length - (n * -1) % length : n % length;
  }

   public LinkedListNode rotate_list(LinkedListNode head, int n) {

     int listSize = 0;
     listSize = getListSize(head);

     n = adjustRotatationsNeeded(n, listSize);

     if (n == 0) {
       return head;
     }

    // Find the startNode of rotated list.
    // If we have 1,2,3,4,5 where n = 2,
    // 4 is the start of rotated list

     LinkedListNode temp = head;
     int rotationsCount = listSize - n - 1;
     while(rotationsCount > 0) {
       temp = temp.next;
       rotationsCount--;
     }

     LinkedListNode new_head = temp.next;
     temp.next = null;

     LinkedListNode tail = new_head;
     while (tail.next != null) {
       tail = tail.next;
     }

     tail.next = head;
     head = new_head;

    return new_head;
  }
}