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

C++语言 码拜 6年前 (2015-05-11) 249次浏览 0个评论
 

/**
 * 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;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明为何加上倒数第二句就能ac了?
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!