LeetCode刷题日记 19. 删除链表的倒数第N个节点

题目给出一个链表，给出一个整数n，要求返回删除了倒数第n个节点的链表。这道题可以使用快慢指针法，让fast先向后移n个节点，然后让快慢指针同时向后移，直到快指针达到最后一个节点。此时，慢指针指向的下一个节点及为需要删除的节点，将其删除，代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(-1); dummy->next = head; //虚拟头节点 ListNode *fast = dummy; //快指针 ListNode *slow = dummy; //慢指针 for(int i = n; i > 0; i--) //根据n，让快指针先走n步 { fast = fast -> next; } while(fast -> next) //当快指针还没有到链表最后一个节点时，快慢指针同时向后移 { fast = fast -> next; slow = slow -> next; } slow -> next = slow -> next -> next; //当快指针达到最后一个节点，slow所指向的节点的后一个节点为需要删除节点，将其删除 return dummy->next; } };

这道题易错点在于，如果链表只有一个节点，n为1，此时，如果不采用虚拟头节点，就会发生报错。