/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
if(n<=0)return NULL;
if(n==0)return NULL;
ListNode dumphead(0);
dumphead.next = head;
ListNode* fast = &dumphead;
ListNode* slow = &dumphead;
while(n--)
{fast = fast->next;}
while(fast->next!=NULL)
{
fast = fast->next;
slow = slow->next;
}
ListNode *tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
head = dumphead.next;//请问为啥要加上这一句呢？这个函数没有对head修改啊。。。
return head;
}
};
|
|
| 8分 |
没有上下文代码，所以没看太明白。
你这个函数的名字叫removeNthFromEnd，估计跟删除有关。 所以，删除之后，head要修改。 |
| 8分 |
函数功能是去除链表倒数第N个结点，算法很简单，就是建两个指针，一个快指针，一个慢指针
快指针先走N步，然后快慢指针同时走，直到快指针的下一个指针为空，则慢指针的下一个指针即为倒数第N个 把它删除即可 具体为什么要这一句 head = dumphead.next; |
|
对 |
|
| 8分 |
head = dumphead.next;//请问为啥要加上这一句呢？这个函数没有对head修改啊。。。
有一种情况 删除的倒数第n个元素是头指针 程序还有问题 假如链表的长度小于n呢 |
| 1分 |
貌似程序问题不少，可以多跑几次，输入不同的长度的结点来测试一下
|
| 8分 |
// 如果slow不动 ， 即slow->next==head 下面语句将delete head ListNode *tmp = slow->next; slow->next = slow->next->next; delete tmp; return head; //这里head是无效指针 |
| 8分 |
不要比较n与链表的长度吗？
|
| 50分 |
dumphead.next = head;
dumphead.next就是指向head 按字面代码来说，那句根本就是不必要的（但是请考虑删除第一个节点的情况） 所以这句代码是必要的，使程序删除第一个节点时程序的正确性！ dumphead next1 next2 如果删除 next1，其实头指针指向next2，但是head依然是指向next1 的内存块的，所以必须把删除后的dumphead->next（即next2地址赋值给head 再有
if(n<=0)return NULL;
//if(n==0)return NULL; //n <= 0判断已经包含了，所以这是多余代码
ListNode dumphead(0);
dumphead.next = head;
ListNode* fast = &dumphead;
ListNode* slow = &dumphead;
//while(n--) //应该判断fast是否为空，空则返回NULL，原因是当n大于head元素个数的时候，将让程序奔溃
while(n-- && fast != NULL)
{fast = fast->next;}
|
| 9分 |
看了各位大神的评论，才发现这道题要考虑的地方还不少
1.注意链表长度小于N的情况！链表长度小于N时,提示，返回NULL 2.保证程序删除第一个节点,即head时，程序的正确性 当删除的是head结点时，显然应该返回head结点的下一个结点！ 下面是自己写的程序，当练练手
/**
http://bbs.csdn.net/topics/391029228
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
using namespace std;
struct ListNode{
ListNode * next;
int value;
};
ListNode* head=new ListNode();
/**
函数：removeNthFromEnd
功能：去除链表倒数第N个结点
*/
ListNode* removeNthFromEnd(ListNode* head, int m)
{
int n=m;
if(n<=0)return NULL;
ListNode * dumphead=new ListNode();;
dumphead->next = head;
ListNode* fast = dumphead;
ListNode* slow = dumphead;
/*
注意链表长度小于N的情况！
链表长度小于N,提示，返回NULL
*/
while(n--)
{
if(NULL!=fast->next)
fast = fast->next;
else{
cout<<"链表长度小于"<<m<<endl;
return NULL;
}
}
while(fast->next!=NULL)
{
fast = fast->next;
slow = slow->next;
}
ListNode *tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
/**
保证程序删除第一个节点,即head时，程序的正确性
当删除的是head结点时，显然应该返回head结点的下一个结点！
*/
head = dumphead->next;
return head;
}
/**
遍历链表
*/
void goThroughList(ListNode *head){
if(NULL==head)
return;
ListNode *test=new ListNode();
test=head;
while(NULL!=test){
cout<<test->value<<endl;
if(NULL==test->next)
break;
else
test=test->next;
}
}
void initList(){
int i = 1;
head->value=i++;
ListNode* index=new ListNode();
index->value=i++;
head->next=index;
for(;i<9;i++){
ListNode *last=new ListNode();
last->value=i;
index->next=last;
index=last;
}
}
int main()
{
initList();
cout<<"原链表"<<endl;
goThroughList(head);
int nth = 10;
head=removeNthFromEnd(head,nth);
if(NULL!=head){
cout<<"去除倒数第"<<nth<<"个结点后的链表"<<endl;
goThroughList(head);
}
system("pause");
return 0;
}
|
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明为何加上倒数第二句就能ac了？！