无锡高端网站设计制作陕西专业网站建设哪家好

想法一 

先用tail指针找尾，计算出节点个数，再根据倒数第N个指定删除

想法二 

根据进阶的要求，只能遍历一遍链表，那刚刚想法一就做不到 

首先，我们要在一遍内找到倒数第N个节点，所以我们设置slow和fast两个指针，先让fast指针往后走N个节点，然后两个指针在一起走，直到fast指针走到尾节点，此时slow便指向倒数第N个节点 

 

然后，找到指定节点后，要分情况删除：头删，中间删除，尾删 

头删：当fast指针为NULL时，则为头删 

 

尾删：当slow指针下一个节点就是fast指针时，则为尾删 

 

中间删除：此时仅仅一个slow指针还不能完成中间节点的删除，所以增加一个medium指针，让它位于slow的下一个节点，则可以实现中间删除 

 

完整代码如下： 

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{struct ListNode* slow = head;struct ListNode* fast = head;struct ListNode* medium = head->next;while (n--){fast = fast->next;}while (fast && fast->next){slow = slow->next;medium = medium->next;fast = fast->next;}if (!fast){//头删head = slow->next;free(slow);}else if(slow->next == fast){//尾删slow->next = NULL;free(fast);}else{//中间删除slow->next = medium->next;free(medium);}return head;
}