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を見つけることができました。
実装
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;
}
}