解法1
解题思路
常见的链表操作为——添加一个哑节点(dummy node) 这个dummy的next指针指向head.如此我们就不需要对头节点进行其他操作了。 但请注意，程序写完一定要delete掉！
代码如下：
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL){}
};
int getLength(ListNode* head, int n)
{
int length;
for(int i = 0; i < n; i++)
{
++length;
head = head->next;
}
return length;
}
ListNode* removeNthNode(ListNode* head, int n)
{
ListNode* dummy = new ListNode(0,head);
int length = getLength(head);
ListNode* cur = dummy;
for(int i = 0; i < length - n + 1; i++)
{
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
int main()
{
//缺测试用例
}
解法2
解题思路
代码如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummy = new ListNode(0);
ListNode *left = dummy;
ListNode *right = dummy;//new两个指针，都指向这个虚拟的头结点
dummy->next = head; //让这个虚拟的头结点指向真正的头结点
//先让快指针向前走n步
for(int i = 0; i < n; i++)
{
right = right->next;
}
//当快指针不是最后一个节点的时候，就让快慢指针同时向后移动
while(right->next)
{
left = left->next;
right = right->next;
}
//当快指针是最后一个节点的时候，就把慢指针后面一个节点删除
left->next = left->next->next;
return dummy->next;
}
};
int main()
{
//缺测试用例
}
