python查找链表中倒数第k个结点
时间: 2024-09-29 08:04:19 浏览: 9
在Python中,查找链表中倒数第k个节点通常需要先遍历链表获取链表的长度,然后从头开始再次遍历链表,这次是在找到第k个节点之后再前进一步,指向的就是倒数第k个节点。这是一个典型的双指针问题,可以使用两个指针p1和p2,初始时p2位于p1之前k步。
以下是实现该功能的一个简单示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_to_last(head, k):
p1 = p2 = head
# 首先移动p2 k步
for _ in range(k):
if not p2:
return None # 如果k大于链表长度,则返回None
p2 = p2.next
# 然后同时移动p1和p2直到p2到达末尾
while p2.next:
p1 = p1.next
p2 = p2.next
return p1 # 返回倒数第k个节点
```
在这个函数中,如果`find_kth_to_last`成功找到了倒数第k个节点,它将返回那个节点;如果没有找到(比如k大于链表长度),则返回`None`。
相关问题
查找链表中倒数第k个结点
要查找链表中倒数第 k 个节点,可以使用双指针的方法。首先定义两个指针,一个指针称为 slow,一个指针称为 fast。将 fast 指针先向前移动 k-1 步,然后 slow 指针从头开始与 fast 指针同时向后移动,直到 fast 指针到达链表末尾。
这时,slow 指针所指的节点就是倒数第 k 个节点。
下面是示例代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_from_end(head, k):
slow = fast = head
for _ in range(k):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
# 创建链表
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# 测试查找倒数第 k 个节点
k = 2
result = find_kth_from_end(head, k)
print("倒数第", k, "个节点的值为:", result.val)
```
查找链表倒数第k个结点
查找链表倒数第k个结点可以使用双指针法。首先定义两个指针p1和p2,都指向链表的头结点。然后将p1指针向前移动k个结点,此时p1和p2之间的距离为k。接着同时移动p1和p2指针,直到p1指向链表的末尾,此时p2指向的结点即为倒数第k个结点。
具体实现代码如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_to_tail(head: ListNode, k: int) -> ListNode:
if not head or k <= 0:
return None
p1 = p2 = head
for i in range(k-1):
if not p1.next:
return None
p1 = p1.next
while p1.next:
p1 = p1.next
p2 = p2.next
return p2
```
其中,head为链表的头结点,k为倒数第k个结点的位置,函数返回倒数第k个结点。如果链表为空或k小于等于0,返回None。