采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。
我们可以设想假设设定了双指针 p 和 q 的话,当 q 指向末尾的 NULL,p 与 q 之间相隔的元素个数为 n 时,那么删除掉 p 的下一个指针就完成了要求。
#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode* p=head;
ListNode* q=head->next;
int num = 0;//计算p和q之间存在几个节点
while (q)
{
if (num <n)
{
q = q->next;
num++;
}
else
{
q = q->next;
p = p->next;
}
}
//删除p后面的一个顶点
ListNode* temp = p->next;
p->next = p->next->next;
delete temp;
return head;
}
};
//测试-----------------
void input(ListNode* l)
{
int num;
while (1)
{
cin >> num;
if (num == -1)
return;
ListNode* newNode = new ListNode(num);
newNode->next = l->next;
l->next = newNode;
}
}
void display(ListNode* l)
{
if (l== NULL)
{
return;
}
cout << l->val;
display(l->next);
}
void test()
{
ListNode* l = new ListNode(0);
input(l);
Solution s;
l=s.removeNthFromEnd(l, 2);
cout << "链表打印:" << endl;
display(l->next);
cout << endl;
}
int main()
{
test();
system("pause");
return 0;
}