题目链接

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

示例1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

提示

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100

  • 1 <= n <= sz

    思路

    思路1：计数

    计算正向第几个结点，删除即可。

    思路2：栈

    将链表全部入栈，再弹出第 n 个元素删除。

    思路3：快慢指针

    以示例一为例：
    0019-删除链表的倒数第n个结点 - 图1

    题解

    思路3：快慢指针

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12.  public:
    13.   ListNode* removeNthFromEnd(ListNode* head, int n) {
    14.       ListNode dummyHead = ListNode();
    15.       dummyHead.next = head;
    16.       ListNode* fast = head;
    17.       ListNode* slow = &dummyHead;
    18.       while (n--) {
    19.           fast = fast->next;
    20.       }
    21.       while (fast) {
    22.           fast = fast->next;
    23.           slow = slow->next;
    24.       }
    25.       slow->next = slow->next->next;
    27.       return dummyHead.next;
    28.   }
    29. };

    复杂度分析

    思路3：快慢指针

  • 时间复杂度：0019-删除链表的倒数第n个结点 - 图2

  • 空间复杂度：0019-删除链表的倒数第n个结点 - 图3