给定一个链表,删除链表的倒数第N个节点并返回链表的头指针
时间: 2024-08-16 15:04:18 浏览: 53
在链表操作中,删除倒数第N个节点是一个常见的问题,特别是当无法直接访问到倒数第N个节点时。解决这个问题的一种常见方法是使用两个指针。这里是一种Python的解决方案:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
# 使用快慢指针法
slow = fast = head
if not head or n == 0:
return head
# 先让fast指针前进n个位置
for _ in range(n):
if fast is None or fast.next is None:
break
fast = fast.next
# 如果n大于链表长度,则直接返回头结点,因为倒数n个元素不存在
if fast is None:
return head
# 同时移动slow和fast,直到fast到达链表尾部
while fast.next is not None:
slow = slow.next
fast = fast.next
# 删除倒数第n个节点,将slow.next指向下一个节点
slow.next = slow.next.next
return head
```
这个函数首先检查特殊情况(如n为0或链表为空),然后使用快慢指针的方式找到倒数第n个节点,最后跳过这个节点并返回新的链表头部。
阅读全文