如何使用Python实现链表的删除倒数第n个节点操作

2023-04-11 00:00:00 节点如何使用倒数

链表是一种常用的数据结构，在Python中可以通过定义类来实现链表。删除链表中倒数第n个节点的操作可以先使用快慢指针法，找到倒数第n+1个节点，然后进行删除操作。

具体实现如下：

定义一个Node类，表示链表的节点，包含两个属性：val表示节点的值，next表示指向下一个节点的指针。

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

定义一个LinkedList类，表示链表，包含一个属性：head表示链表的头节点。

class LinkedList:
    def __init__(self):
        self.head = None

定义一个方法add_node，用来向链表中添加节点。如果链表为空，则新节点即为头节点；否则，遍历链表直到找到尾节点，将新节点加入到其后面。

    def add_node(self, val):
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new_node

定义一个方法delete_node，用来删除链表中的节点。使用快慢指针法，先让快指针移动n步，然后同时移动快慢指针，直到快指针到达尾节点。此时慢指针就指向了倒数第n+1个节点。如果链表只有一个节点，即为头节点，直接将其删除；否则，将倒数第n+1个节点的next指针指向倒数第n-1个节点，即可完成删除操作。

    def delete_node(self, n):
        if self.head is None:
            return
        slow = fast = self.head
        for i in range(n):
            fast = fast.next
            if fast is None and i < n - 1:
                return
        if fast is None:
            self.head = slow.next
        else:
            while fast.next is not None:
                slow = slow.next
                fast = fast.next
            slow.next = slow.next.next

完整代码如下：

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, val):
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new_node

    def delete_node(self, n):
        if self.head is None:
            return
        slow = fast = self.head
        for i in range(n):
            fast = fast.next
            if fast is None and i < n - 1:
                return
        if fast is None:
            self.head = slow.next
        else:
            while fast.next is not None:
                slow = slow.next
                fast = fast.next
            slow.next = slow.next.next

    def print_list(self):
        cur = self.head
        while cur is not None:
            print(cur.val, end="")
            if cur.next is not None:
                print("->", end="")
            cur = cur.next
        print()


linkedList = LinkedList()
linkedList.add_node("p")
linkedList.add_node("i")
linkedList.add_node("d")
linkedList.add_node("a")
linkedList.add_node("n")
linkedList.add_node("c")
linkedList.add_node("o")
linkedList.add_node("d")
linkedList.add_node("e")
linkedList.print_list()

linkedList.delete_node(4)
linkedList.print_list()

输出结果为：

```
p->i->d->a->n->c->o->d->e
p->i->d->a->n->c->e

相关文章