学步园

一、     题目

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

例如： 已知: 1->2->3->4->5,  n = 2.

处理后：1->2->3->5.

      试着遍历一次完成。

二、     分析

看到这道题我第一感觉就是双指针，因为要删除倒数第n个数，所以两个指针的间距也就是这个n，当右边的指针到达末尾处时，那么左指针的下一个指针就是要删除的节点。其实会有下面几种特殊情况:

1、{1,2}，n=1;

2、{1,2}，n=2;

3、{}，0

当然，有人可能会说n可不可以大于节点数，不过这个题目已经限制了n是有效的。

扩展：1、n的值不限制

           2、链表不限于单链表，求删除离头节点倒数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) {
    	if(head==NULL||head->next==NULL) return NULL;
    	
    	ListNode *Rnode = head;
    	ListNode *Lnode = head;
    	
        for(int i=1; i<=n; i++){
        	Rnode = Rnode->next;
        } 
        if(Rnode==NULL){
        	head = head->next;
        	return head;
        }
        while(Rnode->next!=NULL){
        	Lnode = Lnode->next;
        	Rnode = Rnode->next;
        }
    	Lnode->next = Lnode->next->next;
        return head;
    }
};