题目描述

给定一个单向链表，要求删除从结尾数第nn个结点，并返回修改后的表头。
链表结点的定义如下：

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

样例
给定数组单向链表 1->2->3->4->5 ，以及 n = 2 ，修改后的链表为 1->2->3->5。
Note
nn总是合法的。
尝试使用一次遍历完成本题。

1.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *e_head=new ListNode(0);//定义一个保护节点，当链表只有一个节点时起作用
    e_head->next=head;
    ListNode *first=e_head,*second=e_head;
    for(int i=0;i<=n;i++) first=first->next; //first先向前走n步
    for(;first!=NULL;first=first->next)//first走到节点不存在时,second下一个位置就是所求位置
        second=second->next;
        second->next=second->next->next;
        return e_head->next;
    }
};

2.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
   int len=0;
   for(ListNode *p=head;p!=NULL;p=p->next) len++;//找到链表长度
   if(len==n) return head->next;//排除n在head
   int cnt=0;
   for(ListNode *p=head;p!=NULL;p=p->next)
   if(++cnt+n==len) 
   {
    ListNode *q=p->next;
    delete q;
       p->next=p->next->next;
       break;
   }
   return head;
    }
};