Leetcode 19. 删除链表的倒数第N个节点

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析

• 时间复杂度：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)。