问题描述

给定一个链表，随机删除链表中倒数第n个结点，并返回链表的头结点。
链表中的结点个数大于等于n
示例：
给出链表 1->2->3->4->5->null 和 n = 2
删除倒数第2个结点之后，最终得到链表 1->2->3->5->null
要求：
O(n)时间复杂度，一次遍历实现。

题目分析

既然要删除链表的倒数第n个结点，那么就需要先找出链表的倒数第n+1个结点，然后修改这个结点的指向为next->next。
题目要求一次遍历实现，我们可以使用“双指针法”，设置两个指针p1和p2；p1先出发，走到第n+1个结点时，p2再出发。这样，当p2走到链表的尾结点时，p1指向的正好是倒数第n+1个结点。

实现代码

NodeList removeNodeFromEnd( NodeList Head , int n)
{
    NodeList preNode = Head;
    NodeList curNode = Head;
    for(int i=0; i<n; i++){
        curNode = curNode->next;
    }
    if(curNode == null){
        return preNode->next;
    }
    while(curNode!=NULL){
        curNode = curNode->next;
        preNode = preNode->next;
    }
    preNode->next = preNode->next->next;
    return Head;
}

参考链接

LeetCode - 删除链表的倒数第N个节点
删除链表中倒数第n个节点