题目描述

题目链接：19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

例子

例子 1

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

例子 2

Input: head = [1], n = 1 Output: []

例子 3

Input: head = [1,2], n = 1 Output: [1]

Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解题思路

要求删除链表中倒数第 n 个节点，直观的思路是遍历一次链表获取长度 l，再遍历一次将第 l-n 个节点删掉即可。不过题目要求只遍历一次，所以可以用快慢指针的方法，让其直接相隔 n 个节点，这样当快指针到末尾时慢指针会指向第 l-n-1 个节点，将下一个节点删除即可。

代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        int step = 0;
        while (step < n) {
            fast = fast->next;
            step++;
        }
        
        if (!fast) return head->next;

        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;

        return dummy->next;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 19.RemoveNthNodeFromEndOfList.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions