问题描述
给定一个链表,随机删除链表中倒数第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个节点