How to remove the nth node from the end of the list reversing the linked-list?

Question

I want to remove the nth node from the end of the list by reversing the linked list first and then removing the nth node. I know there's a better solution than this, but the way I'm thinking is like reverse LinkedList first and then remove the target index (starting from 1) from the beginning of the list and then covert the list back to the original version.

Here's the code I wrote so far:

from typing import List


class ListNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None


def print_list(head: ListNode) -> None:
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("None")


def insertAtTail(arr: List[int]) -> ListNode:
    head = ListNode(arr)
    if not head:
        print("List is empty.")

    head = ListNode(arr[0])
    for i in arr[1:]:
        last_node = head
        while last_node.next:
            last_node = last_node.next
        last_node.next = ListNode(i)
    return head


def reverse_linkedList(head: ListNode) -> ListNode:
    curr, prev = head, None
    while curr:
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp
    return prev


def remove_nth_node(head: ListNode, n: int) -> ListNode:
    if not head:
        print("Head is empty.")

    if n == 0:
        head = head.next
        return head
    else:
        counter = 1
        curr = head
        while curr and counter < n - 1:  # nth index starts at 1 not 0
            curr = curr.next
            counter += 1

        if curr is None:
            print("Invalid nth.")

        curr.next = curr.next.next
    return head


lst = [7, 3, 9, 2, 5, 0]
nodes = insertAtTail(lst)
print("The original list: ")
print_list(nodes)

print("\nAfter removing specific nth node: ")
node = remove_nth_node(nodes, 3)
print_list(node)

print("\nAfter reversing the list: ")
node = reverse_linkedList(nodes)
print_list(node)

Output:

The original lists are: 
7 -> 3 -> 9 -> 2 -> 5 -> 0 -> None

After removing specific nth node: 
7 -> 3 -> 2 -> 5 -> 0 -> None

After reversing the list: 
0 -> 5 -> 2 -> 3 -> 7 -> None

I want to use that reverse_linkedList function inside of the remove_nth_node function so my output should be:

After removing specific nth node: 
7 -> 3 -> 9 -> 5 -> 0 -> None

Instead of:

After removing specific nth node: 
7 -> 3 -> 2 -> 5 -> 0 -> None

Answer 1

Some issues:

• Your remove_nth_node function removes the same (second) node when passing 1 or 2 as argument for n. As in a comment you write that the nth index starts at 1, I'll assume that 2 should remove the second node, and 1 should remove the first node, so that would be the base case and caller should not pass a value less than 1.

• In remove_nth_node you should not continue with any other statements when you have an exceptional condition (like empty list, or too large value for n), so either add return head, or use an elif chain.

• In the main program, you are not doing what you describe, i.e. you are not first reversing the list before calling remove_nth_node

• In the main program, the variable nodes is not reassigned -- as you assign to a different variable node -- which can be a problem when you call remove_nth_node to remove the head node.

• You write you want to call to reverse_linkedList function inside of the remove_nth_node function, but I would suggest to create a new function, so that you can distinguish between the "normal" remove_nth_node and remove_nth_last_node.

So first correct remove_nth_node as follows:

def remove_nth_node(head: ListNode, n: int) -> ListNode:
    if not head:
        print("Head is empty.")
    elif n < 1:  # invalid
        print("Invalid nth.")
    elif n == 1:  # first
        head = head.next
    else:
        counter = 1
        curr = head
        while curr and counter < n - 1:  # nth index starts at 1 not 0
            curr = curr.next
            counter += 1

        if curr is None:
            print("Invalid nth.")
            return head

        curr.next = curr.next.next
    return head

Then the new remove_nth_last_node function:

def remove_nth_last_node(head: ListNode, n: int) -> ListNode:
    head = reverse_linkedList(head)
    head = remove_nth_node(head, n)
    return reverse_linkedList(head)

And finally, the main driver code to test it:

lst = [7, 3, 9, 2, 5, 0]
head = insertAtTail(lst)
print("The original list: ")
print_list(head)

print("\nAfter removing 3rd last node: ")
head = remove_nth_last_node(head, 3)
print_list(head)