一、题意
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ }
二、思考过程
2.1思路：利用双指针法
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
以上两步的实现：
step1:模拟头节点的创建
typedef struct ListNode ListNode; ListNode *shead; shead=(ListNode *)malloc(sizeof(ListNode)); shead->next=head;//虚拟头节点
step2:定义快慢指针
ListNode *SlowIndex=shead; ListNode *FastIndex=shead;
step3:快指针移动，慢指针同步
while(n--&&FastIndex!=NULL){ FastIndex=FastIndex->next; } FastIndex=FastIndex->next; while(FastIndex!=NULL){ FastIndex=FastIndex->next; SlowIndex=SlowIndex->next; } SlowIndex->next=SlowIndex->next->next;//关键之处
step4：返回头指针
return shead->next;
三、完整代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ typedef struct ListNode ListNode; ListNode *shead; shead=(ListNode *)malloc(sizeof(ListNode)); shead->next=head;//虚拟头节点 ListNode *SlowIndex=shead; ListNode *FastIndex=shead; while(n--&&FastIndex!=NULL){ FastIndex=FastIndex->next; } FastIndex=FastIndex->next; while(FastIndex!=NULL){ FastIndex=FastIndex->next; SlowIndex=SlowIndex->next; } SlowIndex->next=SlowIndex->next->next; return shead->next; }
