删除链表的倒数第n个结点

删除链表的倒数第n个结点

题目描述：编写一个程序，找到两个单链表相交的起始节点。没有就返回null。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

题解思路：先计算链表的总长度，然后用总长度-给出的n，得到要删除的结点的前驱，完成删除操作即可，但是要注意的是删除第一个结点的问题，他没有前驱，要特殊操作，让头指针直接指向第二个节点。

int len(struct ListNode *H)
{
    int count=0;
    struct ListNode *p=H;
    while(p)
    {
        count++;
        p=p->next;
    }
    return count;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int count,len_H;
    struct ListNode* p=head;
    len_H=len(head);
    count=len_H-n;
    if(count==0)
    {
        head=p->next;
    }
    else
    {
        while(p)
        {
            count--;
            if(count==0)
            {
                p->next=p->next->next;
                break;
            }
            p=p->next;
        }
    }
    return head;
}

双指针法：很巧妙，就是设置两个指针，first，second，然后first先走n+1步，然后second和first同步走，直至first走到链尾（NULL）为止，这样两个指针之间相差n+1步，first为NULL，那么second自然指向倒数第n个节点的前驱，值得注意的还是头结点点的删除操作。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* first,*second;
    first=second=head;
    while(first)
    {
        if(n<0)
        {
            second=second->next;
        }
        n--;
        first=first->next;
    }
    if(n==0)
    {
        head=head->next;
    }
    else
    {
        second->next=second->next->next;   
    }
    return head;
}