函数题:求单链表第k个结点的代码
时间: 2024-09-23 19:14:11 浏览: 96
在Python中,可以使用迭代或者递归的方式来解决这个问题,这里提供一种常见的迭代方法,使用两个指针分别表示快慢指针:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def getKthNode(head, k):
if not head or k <= 0:
return None
slow = fast = head
for _ in range(k - 1): # 快指针先走k-1步
fast = fast.next if fast else head
while fast and fast.next: # 当快指针未到末尾,慢指针每次移动一步
slow = slow.next
fast = fast.next.next
return slow if fast else None # 如果快指针到了末尾,说明kth节点就是慢指针指向的
# 使用示例
# 创建链表:1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k = 3
print(getKthNode(head, k)) # 输出:ListNode(3)
```
阅读全文