为何加上倒数第二句就能ac了？

/** * 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; 好困啊现在。。。没精神写代码了原谅我明天写！
	引用 1 楼 u012033027 的回复: 没有上下文代码，所以没看太明白。你这个函数的名字叫removeNthFromEnd，估计跟删除有关。所以，删除之后，head要修改。引用 2 楼 hzy38324 的回复: 函数功能是去除链表倒数第N个结点，算法很简单，就是建两个指针，一个快指针，一个慢指针快指针先走N步，然后快慢指针同时走，直到快指针的下一个指针为空，则慢指针的下一个指针即为倒数第N个把它删除即可具体为什么要这一句 head = dumphead.next; 好困啊现在。。。没精神写代码了原谅我明天写！引用 2 楼 hzy38324 的回复: 函数功能是去除链表倒数第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 你delete一个dumphead元素，当然是修改了链表的数据了（其实也就是修改了head的数据）按字面代码来说，那句根本就是不必要的（但是请考虑删除第一个节点的情况）当删除的是第一个节点的情况下，head头指针指向有变化，所以必须重新指定指针值所以这句代码是必要的，使程序删除第一个节点时程序的正确性！ dumphead next1 next2 head 如果删除 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; }

文章评论已关闭！