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

2023-04-11 00:00:00 节点 链表 倒数

链表删除倒数第N个节点的优化算法是使用双指针，使得遍历一遍就能找到要删除的节点。

具体做法如下：

  1. 定义两个指针p和q，都指向链表的头节点。
  2. 让q先向前移动n步。
  3. 然后同时移动p和q，直到q遍历到链表的尾节点。
  4. 此时p就指向要删除的节点的前一个节点。
  5. 将要删除的节点删除即可。

代码实现如下：

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
    p, q = dummy, dummy

    for i in range(n):
        q = q.next

    while q.next:
        p = p.next
        q = q.next

    p.next = p.next.next
    return dummy.next

例如，给定链表1->2->3->4->5和n=2，要删除倒数第二个节点4，则调用removeNthFromEnd函数，返回的链表为1->2->3->5。

字符串示例：

s = "pidancode.com"
head = ListNode(s[0])
current = head
for i in range(1, len(s)):
    current.next = ListNode(s[i])
    current = current.next
new_head = removeNthFromEnd(head, 5)

while new_head:
    print(new_head.val, end="")
    new_head = new_head.next
# 输出 "pidancode.om"

相关文章