题目

Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

分析

给定一个链表，移除从队尾向前数的第n个节点。
由于是链表，只能从前向后寻找数据，所以先遍历看一共多少数据，即可知道要移除的倒数第几个数字是正数的第几个数字。
之后寻找该几点和其前节点，然后替换next指针即可，C代码如下，已通过。
也可以使用两个指针，先让一个走n步，另一个接着走。那么当第一个指针达到链表尾部时候，第二个指针指向第n个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode * p=head, *q=head;
    int length=0;
    while(p!=NULL)
    {
        p=p->next;
        length++;
    }
    p=head;
    if(n>length)
        n=1;
    else
        n=length-n+1;
    while(n-1>0&&p->next!=NULL)
    {
        q=p;
        p=p->next;
        n--;
    }
    if(q==p)
    {
        head=head->next;
    }
    else
    {
        q->next=p->next;
    }
    return head;
}