如何使用Python实现链表的寻找倒数第k个节点的中间节点操作
首先，我们需要先定义一个链表节点类Node，该类包含两个属性：val（节点的值）和next（指向下一个节点的指针）。
class Node: def __init__(self, val=None): self.val = val self.next = None
接下来，我们实现链表的寻找倒数第k个节点和中间节点的操作。
寻找倒数第k个节点的思路是先用快指针和慢指针将它们之间的距离保持为k，然后同时向后移动这两个指针，当快指针到达链表结尾时，慢指针所指向的节点即为倒数第k个节点。
def find_kth_from_end(head, k):
fast, slow = head, head
for i in range(k):
if not fast:
return None # 链表长度小于k，返回None
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
寻找中间节点的思路是同样使用快指针和慢指针，但快指针的步长变为2，慢指针的步长为1，当快指针到达链表结尾时，慢指针所指向的节点即为链表的中间节点。
def find_middle_node(head):
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
下面是完整的代码示例：
class Node: def __init__(self, val=None): self.val = val self.next = None def find_kth_from_end(head, k): fast, slow = head, head for i in range(k): if not fast: return None # 链表长度小于k，返回None fast = fast.next while fast: fast = fast.next slow = slow.next return slow def find_middle_node(head): fast, slow = head, head while fast and fast.next: fast = fast.next.next slow = slow.next return slow # 测试代码 if __name__ == '__main__': head = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) head.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 print("链表的倒数第2个节点为：", find_kth_from_end(head, 2).val) # 输出4 print("链表的中间节点为：", find_middle_node(head).val) # 输出3
相关文章