给定一个单向列表,请编写一个函数,删除列表的倒数第k个节点。要求:空间复杂度为O(1),时间复杂度为O(n),且只能遍历一次列表。
时间: 2024-10-19 07:07:14 浏览: 26
C++实现单链表删除倒数第k个节点的方法
为了在一个单向链表中删除倒数第k个节点,并满足空间复杂度为O(1)和时间复杂度为O(n),我们需要采用双指针的方法。假设有一个指向当前节点的指针p和一个距离指针q,初始时p都指向头节点,q指向头节点的前一个节点。
算法步骤如下:
1. 初始化两个指针p和q,分别指向链表的头节点和空(null),然后移动p k+1次,因为我们需要跳过前k个节点。
2. 当p到达链表尾部时,q就指向了倒数第k个节点的前一个节点。
3. 将q指向的节点的下一个节点赋给q指向的节点,这样就删除了倒数第k个节点,同时保持p和q的位置不变。
4. 返回原链表头部节点作为结果。
以下是伪代码形式:
```python
def removeKthFromEnd(head, k):
if head is None or k <= 0:
return head
p = head
q = None
for _ in range(k + 1):
if p.next is None:
break
p = p.next
if p is None:
return head.next
while p.next is not None:
p = p.next
q = q.next
q.next = q.next.next
return head
```
阅读全文