删除链表中倒数第n个节点

问题描述：

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

注意事项：链表中的节点个数大于等于n

给出链表1->2->3->4->5->null和 n = 2.

删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.

思路：

       主要用两个指针，先让第一个指针指向第n个节点时，让第二个指针指向头节点，再让第二个与第一个同时开始走，两个指针始终相差n步，当第一个指向最后一个节点的时候，恰好第二个指针指向倒数n+1个，然后覆盖删除。

代码：

/**  * Definition of ListNode  * class ListNode {  * public:  *     int val;  *     ListNode *next;  *     ListNode(int val) {  *         this->val = val;  *         this->next = NULL;  *     }  * }  */ class Solution { public:     /**      * @param head: The first node of linked list.      * @param n: An integer.      * @return: The head of linked list.      */     ListNode *removeNthFromEnd(ListNode *head, int n) {       ListNode *p1 = head;       ListNode *p2 = head;        if (n <= 0 || head == NULL) return head;         while (n > 0 && p1 != NULL) {             p1 = p1->next;             n--;         }    //找到第n个节点         if (p1 == NULL) {             return head->next; //返回除头节点外的剩余节点                 }         while (p1->next != NULL) {             p1 = p1->next;             p2 = p2->next;         }    //两个指针相隔n，一起移动         p2->next=p2->next->next;         return head;                 // write your code here     } };

个人感悟：

        建立思路很重要，用到了两个指针，感觉挺有趣。