Python中链表的删除倒数第n个节点的优化算法

2023-04-11 00:00:00 算法 节点 倒数

一个简单的方法是遍历一遍链表，获取链表的长度，然后再找到倒数第n个节点进行删除。但是这种方法需要遍历两遍链表，时间复杂度为O(n)，不够高效。

更优化的方法可以使用双指针，一个指针指向链表的第一个节点，一个指针指向第n个节点，然后同时向后移动两个指针，直到第n个指针指向链表的尾节点。此时第一个指针指向的就是倒数第n个节点。

代码演示如下：

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    for i in range(n+1):
        second = second.next
    while second:
        first = first.next
        second = second.next
    first.next = first.next.next
    return dummy.next

# 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
current = head
for i in range(2, 6):
    node = ListNode(i)
    current.next = node
    current = node

# 删除倒数第2个节点
head = removeNthFromEnd(head, 2)

# 输出链表中的值
while head:
    print(head.val)
    head = head.next

输出结果为：

1
2
3
5

在这个例子中，我们首先创建了一个链表1 -> 2 -> 3 -> 4 -> 5，然后删除了倒数第2个节点。输出结果表明，删除操作成功，链表变为1 -> 2 -> 3 -> 5。

相关文章