LeetCode初级-删除链表的倒数第N个节点

题目：

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例 :

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

题目分析：

分析见我的注释，我觉得够详细了。

（PS：初次接触链表，原谅我只想到了一个指针额，进阶想了半天，最后看的网上的代码）

C++代码如下：

我的想法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 1;
        ListNode *p = head;
        while (p->next != 0) {
            length++;
            p = p->next;
        }
        
        // 只有一个节点，直接返回p的下一个指针，即空链表
        if (length == 1) {
            return p->next;
        }
        
        p = head;
        // n=1时，删除最后一个节点，情况单独考虑
        if (n == 1) {
            for (int i = 1;i <= length;++i) {
                if (i == length - n) {
                    p->next = 0;
                    return head;
                }
                p = p->next;
            }
        }
        
        // 普通情况
        for (int i = 1;i <= length;++i) {
            if (i == length - n + 1) {
                if (p->next != 0) {
                    p->val = p->next->val;
                    p->next = p->next->next;
                    break;
                }
            }
            p = p->next;
        }
        return head;
    }
};

又一次惊呆？瞎写的不抱啥希望，没想到会100%？！

网上更好的解法：（进阶）

链表的题目基本上都是优先考虑双指针。一个指针先走N步，然后两个指针同步移动到链表末尾，移除前一个指针所指着的节点即可。注意一下边界问题就行。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    //如果链表结点个数为0，直接返回 
    if(n==0){
        return head;
    }
    
    //fastp为快指针，slowp为慢指针（用于指向待删除结点），slowp指向待删除结点的前驱结点。 
    struct ListNode *fastp=NULL,*slowp=NULL,*slowq=NULL;
    //先让快指针后跑n个结点 
    for(fastp=head;n>0;fastp=fastp->next,n--);
    slowp=head;
    //然后让快指针和慢指针一起向后跑，slowp为slowq的联动指针
    //当快指针跑到NULL时停止，这时候快指针一定指向待删除结点 
    while(fastp){
        slowq=slowp;
        slowp=slowp->next;
        fastp=fastp->next;
    }
    //如果要删除的结点为头结点，需要单独处理。否则，利用slowq->next=slowp->next即可删除结点 
    if(slowp==head){
        head=head->next;
    }else{
         slowq->next=slowp->next;  
          free(slowp);
    }
    return head;
    }
};