题目

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

示例 1：

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

屏幕截图 2022-05-20 225913.jpg
示例 2：

  1. 输入：head = [1], n = 1
  2. 输出：[]

示例 3：

  1. 输入：head = [1,2], n = 1
  2. 输出：[1]

提示：

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

  • 1 <= n <= sz


    进阶：你能尝试使用一趟扫描实现吗？

    解题方法

    双指针法

    构建虚拟节点，使双指针间隔n个节点后同时移动，当fast节点移动到链表尾部后，对slow节点的下一个节点删除。
    时间复杂度O(n)，空间复杂度O(1)。

    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* _head = new ListNode();
    15.       _head->next = head;
    16.       ListNode* fast = _head;
    17.       ListNode* slow = _head;
    18.       for(int i = 0; i<n; i++) {
    19.           fast = fast->next;
    20.       }
    21.       while(fast->next != nullptr) {
    22.           fast = fast->next;
    23.           slow = slow->next;
    24.       }
    26.       slow->next = slow->next->next;
    28.       return _head->next;
    29.   }
    30. };