[Leetcode]删除链表的倒数第N个节点

[Leetcode]删除链表的倒数第N个节点

Leetcode-删除链表的倒数第N个节点

题目描述

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

示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明： 给定的 n 保证是有效的。

进阶： 你能尝试使用一趟扫描实现吗？

解题思路

两次遍历，先遍历一次获得链表长度 len，然后从头结点向后移动 len - n 个节点，就是倒数第 n 个节点。一次遍历，使用两个指针p、q，初始时都指向头结点，q先向后移动n个节点，此时 q 指针落 p 指针 n 个节点，然后在一起后移，那么当 q 指向链表尾节点时，p 正好指向倒数第 n 个节点。

实现代码

// 两次遍历 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int len=0; ListNode*p=head; for(;p!=NULL;p=p->next) len++; p=head; ListNode*pre=NULL;//要删除节点的前一个节点 for(int i=0;i<len-n;i++){ if(i==len-n-1) pre=p; p=p->next; } if(p==head)//要删除的节点为头结点 head=head->next; else pre->next=p->next; return head; } }; // 一次遍历 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode*p=head; ListNode*q=head; for(int i=0;i<n;i++)//q指针落p指针n个节点，当q指向链表尾时，p指向倒数第n个节点 q=q->next; ListNode*pre=NULL;//要删除节点的前一个节点 while(q!=NULL){ if(q->next==NULL) pre=p; p=p->next; q=q->next; } if(p==head)//要删除的节点为头结点 head=head->next; else pre->next=p->next; return head; } };