Pythonで連結リストの末尾からN番目のノードを削除する方法

連結リストがあるとします。このリストの末尾からN番目のノードを削除し、削除後のリストの先頭（head）を返す必要があります。例えば、リストが [1, 2, 3, 4, 5, 6] で n = 3 の場合、返されるリストは [1, 2, 3, 5, 6] となります。

解法のアプローチ

この問題は「two-pointer（双ポインタ）」テクニックを使うことで効率的に解決できます。以下の手順で処理を行います。

1. head の後にノードが存在しない場合（要素が1つのみの場合）、None を返します。
2. front と back の両方を head に設定し、counter を 0、flag を false に初期化します。
3. counter が n 以下である間、front を1つずつ前に進めます。このとき、front が存在しなくなったら flag を true に設定してループを抜けます。
4. その後、front が存在する間、front と back を同時に1つずつ進めます。これにより、back は削除対象ノードの一つ手前の位置に到達します。
5. flag が false の場合（削除対象が先頭以外の場合）：temp を back の次のノードとし、back.next を temp.next につなぎ替えることで、対象ノードをリストから切り離します。
6. flag が true の場合（削除対象が先頭の場合）：head を head.next に更新します。
7. 最後に head を返します。

Pythonでの実装例

以下の実装を見て、理解を深めましょう。

class ListNode:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next
def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head
def print_list(head):
    ptr = head
    print('[', end = "")
    while ptr:
        print(ptr.val, end = ", ")
        ptr = ptr.next
    print(']')
class Solution(object):
    def removeNthFromEnd(self, head, n):
        if not head.next:
            return None
        front=head
        back = head
        counter = 0
        flag = False
        while counter<=n:
            if(not front):
                flag = True
                break
            front = front.next
            counter+=1
        while front:
            front = front.next
            back = back.next
        if not flag:
            temp = back.next
            back.next = temp.next
            temp.next = None
        else:
            head = head.next
        return head
head = make_list([1,2,3,4,5,6])
ob1 = Solution()
print_list(ob1.removeNthFromEnd(head, 3))

入力

[1,2,3,4,5,6]
3

出力

[1,2,3,5,6]