如何使用Python实现链表的寻找倒数第k个节点的删除操作
链表的寻找倒数第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
相关文章