如何从反转链表的列表末尾删除第 n 个节点？

Question

我想通过先反转链表然后删除第n个节点来删除列表末尾的第n个节点。我知道有比这更好的解决方案，但我的想法是先反转 LinkedList，然后从列表的开头删除目标索引（从 1 开始），然后将列表隐藏回原始版本。

这是我目前编写的代码：


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

我想在 remove_nth_node 函数中使用那个 reverse_linkedList 函数，所以我的输出应该是：


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

而不是：


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

Answer 1

一些问题：

您的 remove_nth_node 函数在传递 1 或 2 作为 n 的参数时删除相同的（第二个）节点。正如您在评论中写的那样，第 n 个索引从 1 开始，我假设 2 应该删除 second 节点，而 1 应该删除first 节点，因此这是基本情况，调用者不应传递小于 1 的值。
在 remove_nth_node 中，当出现异常情况时（例如空列表或 n 的值太大），您不应继续任何其他语句，因此要么添加return head，或使用 elif 链。
在主程序中，您没有按照您的描述进行操作，即您没有在调用 remove_nth_node
之前先反转列表
在主程序中，变量 nodes 没有被重新分配——当你分配给另一个变量 node 时——当你调用 remove_nth_node删除头节点。
你写你想在remove_nth_node函数里面调用reverse_linkedList函数，但是我建议创建一个新函数，这样你就可以区分“正常”remove_nth_node 和 remove_nth_last_node.

所以先更正remove_nth_node如下：

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

然后是新的remove_nth_last_node函数：

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

最后，测试它的主要驱动程序代码：

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)

如何从反转链表的列表末尾删除第 n 个节点？

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

python

linked-list

nodes

reverse

singly-linked-list