/*****************************************************************************************
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.
*****************************************************************************************/
#include<stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
        if(n <= 0)return head;
        struct ListNode *p = head;
    for(;n > 0 && p!= NULL;n--)p = p->next;
    
    if(n > 0)return head;//n过大，比链表的实际长度大
    if(p == NULL){//要删除的是头结点
        p = head;
        head = head->next;
        free(p);
        return head;
    }

    struct ListNode *f = head;//第二个指针
    while(p->next != NULL){//两个指针一起移动
        p = p->next;
        f = f->next;
    }
    p = f->next;
    f->next = p->next;
    free(p);
    return head;
}

void main(){
    int k = 5;
    struct ListNode *l = (struct ListNode *)malloc(sizeof(struct ListNode));
    l->val = k;
    l->next = NULL;
    while(k--){
        struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
        p->val = k;
        p->next = l;
        l = p;
    }

    struct ListNode *r = l;
    while(r != NULL){
        printf("%d ",r->val);
        r = r->next;
    }
    printf("\n");

    r = removeNthFromEnd(l,3);
    
    while(r != NULL){
        printf("%d ",r->val);
        l = r;
        r = r->next;
        free(l);
    }
}