アルゴリズム体操13

Nth from the Last Node (Easy)

説明

Singly Linked Listの headノードと、整数nが渡されるので、
最後からn番目のノードを返すアルゴリズムを実装してみましょう(nが範囲外の場合はnullを返します)。

Solution

考え方は、nノード離れた2つのポインター使っていきます。
1つ目のポインタはheadを指し、二つ目はn番目のノードを指すように最初に設定します(初期設定)。
もし二つ目のノードが初期設定の際に、リストの最終地点であるnullに達した場合はnullを返します(out-of-bounds)。
次に、ループで2つ目のポインターが最終地点に到達するまで、両方のポインターを前方に移動させていきます。
ループ終了後は、最初のポインターは最後からn番目のノードを指すことになるので、そのポインタを返します。

Runtime Complexity O(n)

Singley Linked List　に対して線形走査するので実行時間はO(n)となります。

Space Complexity O(1)

二つのポインタを使うのでメモリ効率はO(1)の定数となります。

例

3番目の最後のノード（n = 3）を検索する以下のリストの例を見てみましょう。

初期設定として、片方のポインタをnノード分移動させます。

先に進めてあるポインタが最終地点のnullに到達するまで両方のポインタを前に進めていきます。



これで、最後から3番目のnodeを見つけることができました。

実装

lastNthFromList.java

class lastNthFromList{
  public LinkedListNode FindNthFromLast(LinkedListNode head,int n) {

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

    LinkedListNode targetNode = head;
    LinkedListNode searchNode = head;

    while (searchNode != null && n != 0) {
      searchNode = searchNode.next;
      n--;
    }

    if (n != 0) return null; // check out-of-bounds

    while(searchNode != null) {
      targetNode = targetNode.next;
      searchNode = searchNode.next;
    }

    return targetNode;
  }
}