该题运用了双指针的办法
- 定义两个指针ptr1和ptr2,先让ptr2向前走n步
- ptr1和ptr2同时向前走,当ptr2指向null的时候,ptr1指向的就是倒数第n个结点。
- 删除ptr1指向的结点(我采用的方法是:记录ptr1的前一个结点,然后让其指向ptr1的下一个结点)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(NULL == head || NULL == head->next) return NULL;
ListNode* p1 = NULL; //记录p2的前一个结点
ListNode* p2 = head; //指向要删除的结点
ListNode* p3 = head; //需要向前走n步的结点
//p3向前走n步
while(n--) p3 = p3->next;
//p2、p3同时向前走,p1始终指向p2的前一个结点
while(p3 != NULL)
{
p1 = p2;
p2 = p2->next;
p3 = p3->next;
}
//如果要删除的结点就是头节点,那此时p1=null,只需让头节点向后移动,再删除原来的头节点
if(p1 == NULL)
{
ListNode* pDel = head;
head = head->next;
delete pDel;
}
else //如果要删除的不是头节点,那么只需要让被删除结点的前一个结点指向被删除结点的后一个结点,即让p1的下一个结点为p2的下一个结点,删除p2
{
p1->next = p2->next;
delete p2;
}
return head;
}
};