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

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

链表的寻找倒数第k个节点可以使用双指针法,首先将两个指针都指向链表的头节点,然后让其中一个指针先向前移动k-1步,然后两个指针同时向前遍历链表,当先移动的指针指向链表末尾时,后一个指针指向的节点即为所求的倒数第k个节点。

删除操作可以在寻找到倒数第k个节点后,将其前一个节点的next指针指向其后一个节点即可。

以下是Python代码示例:

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

def remove_kth_from_end(head: ListNode, k: int) -> ListNode:
    # 使用双指针法寻找倒数第k个节点
    slow, fast = head, head
    for i in range(k-1):
        fast = fast.next
    prev = None
    while fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next
    # 删除倒数第k个节点
    if not prev:
        head = head.next
    else:
        prev.next = slow.next
    return head

# 示例
if __name__ == '__main__':
    head = ListNode('p')
    node1 = ListNode('i')
    node2 = ListNode('d')
    node3 = ListNode('a')
    node4 = ListNode('n')
    node5 = ListNode('c')
    node6 = ListNode('o')
    node7 = ListNode('d')
    head.next = node1
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node6
    node6.next = node7
    new_head = remove_kth_from_end(head, 3)
    while new_head:
        print(new_head.val, end='')
        new_head = new_head.next
    # 输出:pidanod

相关文章