アルゴリズム体操14

#Swap Nth Node with Head (Easy)

##説明
Singly Linked Listの head と 整数「N」が引数として渡されます。
head と head からN番目のノードと交換します。返り値は新しいLinked listのheadです。
##例
N = 4の例を見てみましょう。

head　を一番目として４番目のノードの28とheadの7を交換するので以下の様になります。

##Solution
###Runtime Complexity O(n)
Linked List に対して走査する必要があるので最悪O(n)かかります。
###Space Complexity O(1)
複数のポインタのみを使用するので、メモリ効率はO(1)となります。

###Step By Step
二つのポインタを用意します。

currentのポインタがN番目のノードを指すまでループします。

currentのポインタが４番目のノードを指すので、ここでループを止めます。

ここからは、ノードの交換をしていきます。




ここで、Swapping できたので、currentのポインタを返します。

###実装

SwapNth.java

class SwapNth{
  // Node indices starts from 1.
  public LinkedListNode SwapNthNode(LinkedListNode head, int n) {

    if (head == null || n < 1) return head; // Edge case

    LinkedListNode cur = head;
    LinkedListNode prev = null;

    int count = 1;

    while (count < n && cur != null) {
      prev = cur;
      cur = cur.next;
      count++;
    }

    if (cur == null) return head;

    // Swapping
    prev.next = head;
    LinkedListNode temp = head.next;
    head.next = cur.next;
    cur.next = temp;
    
    return cur;
  }
} 

###感想
Linked Listに対してSwapping や Sorting などの単純操作を適用したい場合は
複数のポインタを活用することで解決策が見えてくると思います。