题目：

 

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

 样例

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

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

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

解题：

要删除倒数第n个节点，我们要找到其前面一个节点，也就是倒数第n+1的节点，找到这个节点就可以进行删除。和上题的思想很类似，

定义两个指针，p和cur，cur指针向前走，走了n+1步后，p指针开始走，当cur走到结束时候的，p指向倒数n+1的节点

程序中注释部分要注意，当删除的是第一个节点时候，找不到其前一个节点，通过n==1的时候做判断

这里要注意在只有一个节点，也让你删除这个节点，好像只有单独考虑的，题目的节点数大于等于n，没有考虑节点数小于n的情况

Java程序：

/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param head: The first node of linked list.     * @param n: An integer.     * @return: The head of linked list.     */    ListNode removeNthFromEnd(ListNode head, int n) {        // write your code here        ListNode p = new ListNode(0);        p.next = head;        ListNode cur = new ListNode(0);        cur.next = head;        cur = cur.next;        if(n==1 && head.next==null)            return null;        while(cur!=null){            if(n>0){                cur = cur.next;                n--;            }else if(n==0){                cur = cur.next;                head = head.next;                        }            if(cur.next==null){
    // cur运行到最后一个节点                if(n==1)//说明head指针没有移动，结合cur可知道，删除的是第一个节点，                    return p.next.next;                 if(head.next.next==null)                    head.next = null;//删除的是最后一个节点                else                    head.next = head.next.next;//删除的是中间部分的节点                break;            }                                    }        return p.next;    }}

总耗时: 2934 ms

Python程序：

"""Definition of ListNodeclass ListNode(object):    def __init__(self, val, next=None):        self.val = val        self.next = next"""class Solution:    """    @param head: The first node of linked list.    @param n: An integer.    @return: The head of linked list.    """    def removeNthFromEnd(self, head, n):        # write your code here        p = ListNode(0)        p.next = head        cur = ListNode(0)        cur.next = head        cur = cur.next        if n==1 and head.next==None:            return None        while cur!=None:            if n>0:                cur = cur.next                n-=1            elif n==0:                 cur = cur.next                 head = head.next            if cur.next==None:                if n==1:                    return p.next.next                if head.next.next==None:                    head.next=None                else:                    head.next = head.next.next                break        return p.next

总耗时: 519 ms