1.题目描述
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]输入：head = [1], n = 1
输出：[]输入：head = [1,2], n = 1
输出：[1]提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
2.思路分析
2.1 栈
在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
-
定义dummy节点,并指向头结点,如图:
-
遍历链表将所有节依次入栈,如图:
-
依次弹出栈内元素,第n个节点即为需要删除的元素,如图:
-
目前栈顶元素即为删除元素的前一个元素,删除元素,并返回结果,如图:
2.2 双指针
如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
举个栗子,删除链表的倒数第2个元素,步骤如下:
-
定义fast指针和slow指针，初始值为虚拟头结点，如图：
-
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
-
fast和slow同时移动，直到fast指向末尾，如图：
-
删除slow指向的下一个节点，返回结果, dummy.next如图：
3.代码实现
3.1 栈
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
stack = []
cur = dummy
while cur:
stack.append(cur)
cur = cur.next
for i in range(1, n+1):
stack.pop()
prev = stack[-1]
prev.next = prev.next.next
return dummy.next
复杂度分析
- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。
3.2 双指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 设置虚拟头结点,双指针
dummy_head = ListNode(next=head)
fast, slow = dummy_head,dummy_head
# fast指针先走n步
while n !=0:
fast = fast.next
n -= 1
while fast.next != None:
fast = fast.next
slow = slow.next
# 遍历结束,删除节点
slow.next = slow.next.next
return dummy_head.next
复杂度分析
- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。