给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点,n=2,用Python代码编写
时间: 2024-09-02 19:02:23 浏览: 52
python实现获取单向链表倒数第k个结点的值示例
为了删除链表的倒数第 n 个节点,我们可以使用两个指针技巧。第一个指针先向前移动 n 个节点,然后同时开始移动,当第一个指针到达链表尾部时,第二个指针正好指向需要删除的节点前一个节点。接下来我们从第二个指针处断开链表并释放被删除节点。
以下是 Python 的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
if not head or not head.next or n == 1:
return head
# 创建快慢指针,快指针走 n 步
fast = head
for _ in range(n):
fast = fast.next
# 如果快慢指针相遇,说明链表长度小于 n+1,直接返回原链表
if not fast.next:
return head
# 快慢指针分别走到链表尾部和倒数第 n 个位置
slow = head
while fast.next:
fast = fast.next
slow = slow.next
# 删除倒数第 n 个节点
slow.next = slow.next.next
return head
# 示例
# 1 -> 2 -> 3 -> 4 -> 5 (给定 n=2)
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)
new_head = removeNthFromEnd(head, 2)
```
在这个代码中,`removeNthFromEnd` 函数接收链表的头节点和 n 参数,然后返回处理后的链表头节点。请注意,这个函数假设输入合法,即链表至少有 n+1 个节点。如果需要处理边界条件,可以添加适当的错误检查和处理。
阅读全文