19. 删除链表的倒数第 n 个结点
时间: 2023-12-23 18:01:11 浏览: 33
删除链表的倒数第 n 个结点可以通过双指针法来实现。首先定义一个虚拟头结点dummy,然后设置两个指针slow和fast,初始时都指向dummy。接着将fast指针向前移动n+1步,然后slow和fast指针一起向前移动,直到fast指针指向空或者到达链表末尾。此时slow指针所指向的结点就是要删除的倒数第n个结点的前一个结点。
然后,我们可以进行删除操作,将slow指针所指结点的next指针指向下下个结点,从而删除倒数第n个结点。最后返回dummy.next即可得到删除倒数第n个结点后的链表。
但是需要注意的是,当要删除的是头结点时,需要单独处理,可以设置一个哨兵结点来避免头结点的特殊情况。
通过双指针法,可以以O(n)的时间复杂度和O(1)的空间复杂度完成删除链表的倒数第n个结点的操作。这种方法的关键在于利用快慢指针的思想,使得在一次遍历中即可完成删除操作,避免了遍历两次链表或使用额外的空间。
相关问题
19. 删除链表的倒数第 N 个结点
好的,我的回答如下:
可以使用双指针来解决这个问题。首先让一个指针先走 n 步,然后让另一个指针从头开始和第一个指针一起走,直到第一个指针到达链表末尾。此时第二个指针所指向的结点就是要删除的结点的前一个结点,可以通过修改指针的方式来删除该结点。
具体实现可以参考以下代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
first = dummy
second = dummy
for i in range(n):
first = first.next
while first.next is not None:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next
```
java编写删除链表倒数第n个结点的元素
删除链表倒数第n个结点的元素,可以采用双指针的方法。
1. 定义两个指针 p 和 q,初始都指向头结点。
2. 将 q 向后移动 n 个结点。
3. 当 q 到达链表末尾时,p 恰好指向要删除的结点的前一个结点。
4. 删除 p 的下一个结点即可。
下面是 Java 代码实现:
```java
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
ListNode q = head;
for (int i = 0; i < n; i++) {
q = q.next;
}
if (q == null) { // 删除头结点的情况
return head.next;
}
while (q.next != null) {
p = p.next;
q = q.next;
}
p.next = p.next.next;
return head;
}
```
注意:需要考虑删除头结点的情况。如果 q 到达链表末尾时,p 恰好指向头结点,需要返回 head.next。