当前位置:首页 > 开发语言/框架 > C++

为什么加上倒数第二句就能ac了

优良自学吧提供为什么加上倒数第二句就能ac了,为何加上倒数第二句就能ac了? /**  * Definition for singly-linked list.  * struct ListNode {  *  &nb

为何加上倒数第二句就能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;
    }
};


------解决思路----------------------
没有上下文代码,所以没看太明白。
你这个函数的名字叫removeNthFromEnd,估计跟删除有关。
所以,删除之后,head要修改。
------解决思路----------------------
函数功能是去除链表倒数第N个结点,算法很简单,就是建两个指针,一个快指针,一个慢指针
快指针先走N步,然后快慢指针同时走,直到快指针的下一个指针为空,则慢指针的下一个指针即为倒数第N个
把它删除即可

具体为什么要这一句 head = dumphead.next;
好困啊现在。。。没精神写代码了
原谅我明天写!
------解决思路----------------------
head = dumphead.next;//请问为啥要加上这一句呢?这个函数没有对head修改啊。。。

有一种情况 删除的倒数第n个元素是头指针
那么新的头指针应该是指向下一个元素了。

程序还有问题 假如链表的长度小于n呢

------解决思路----------------------
貌似程序问题不少,可以多跑几次,输入不同的长度的结点来测试一下
------解决思路----------------------


// 如果slow不动 , 即slow->next==head 下面语句将delete head
 ListNode *tmp = slow->next;
 slow->next = slow->next->next;
 delete tmp;
return head; //这里head是无效指针

------解决思路----------------------
不要比较n与链表的长度吗?
------解决思路----------------------
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;}

------解决思路----------------------
看了各位大神的评论,才发现这道题要考虑的地方还不少
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;
}

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢