LeetCode #19. Remove Nth Node From End of List プログラミング練習

問題：

難易度:　medium
入力:　ListNode, n
目的: 入力リストの後ろからn番目のノードを取り除け
出力:　ListNode

LinkedListの問題です。
非情報系出身者にはあまり見ないデータ型かもしれませんが、
コーディング面接にはよく出るタイプなので必ず知っておきたい型です。
LinkedListはArrayと違い、一つ先のノードしかアクセスできません。
つまりn番目のノードにアクセスしたい場合は最初のノードからn回アクセスしなければならないのです。
前のノードにもアクセスできないので後ろから数える事も出来ません。
長さも取得できないので後ろからn番目が前から数えて何番目のノードなのかがこの問題の難点です。

よくある方法としては、まずlistの長さを取得するためforで回します。
それで目標ノードが前から何番目なのかがわかるのでもう一度loopすれば答えが出ます。
しかしTimeがO(n^2)となってしまう為あまりいい方法ではありません。

注意すべき事:　

• nが入力されたlistの長さより大きい場合はnullを返す。

以下回答です。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode left = head;
        ListNode right = head;
        for (int i=0; i<n; i++) {
            right = right.next;
        }
        if (right == null) return head.next;
        while (right.next != null) {
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;
        return head;
    }
}

ポインタを二つ用意し、前のポインタは先に進み、後ろのポインタは前のポインタよりn個遅れて進みます。
前のポインタがlistの最後に到達した時、後ろのポインタが指すノードがターゲットになります。
後は目標ノードをスキップすれば完了です。
Time O(n)で解けます。

今日は以上。
よいプログラミング生活を！