[LeetCode] 19. Remove Nth Node From End of List

[Animenzzzz]

Description
Given a linked list, remove the n-th node from the end of list and return its head.

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.

Follow up:

Could you do this in one pass?

解题思路：这题需要一次遍历完成，所以不能完全统计出链表的长度。
使用两个指针：
current：从头开始位移为1的指针
npoint：移动了n步的指针
则：若npoint为空了，说明删除的是头结点，直接返回head->next；若npoint不为空，则current和npoint同时一步一步的位移，直到npoint为空。当npoint为空时，current即为需要删除的节点

此题思路很奇妙，想出来之后实现起来不难，一次A

C解题：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* npoint = head;
    struct ListNode* current = head;
    struct ListNode* currentPre;
    //如果移完n步为nil，那么删除头结点
    while(n){
        npoint = npoint->next;
        if (!npoint)
        {
            return head->next;
        }
        n--;
    }
    while (npoint)
    {
        currentPre = current;
        current = current->next;
        npoint = npoint->next;
        if (!npoint)//删除的是当前的节点
        {
            currentPre -> next = current->next;
            break;
        }
    }
    return head;
}