问题：
递归地从链表中删除数据
胡鸿志
我有一个链表定义为
struct Node{
int data;
Node *next;
};
struct LinkedList{
Node *head;
};
我希望递归地遍历我的链表，删除具有指定数据类型的节点（并正确地重新加入节点）。我找到了迭代的方法，但我一直在努力递归。到目前为止，我得到的是：
void deleteNodeRecursively(LinkedList* list, int value){
if (list->head==NULL){
return;
} else if (list->head->data==value){
list->head=list->head->next;
deleteNodeRecursively(list,value);
} else {
}
}
基本上，我的策略是确定头部是否有数据。如果是这样，我就用下一个节点替换头部。问题是else语句，我知道我必须“移动”到下一个节点。我不仅要转到下一个节点，还要确保它是LinkedList格式的，这样我才能正确使用头部。我不知道如何在不删除所有列表的情况下继续前进。我对复印有模糊的想法？我不太确定现在该怎么办。
编辑：我不想编辑我的结构定义，因为我在其他程序中使用它们。
共有2个答案
长孙弘盛
我正在努力递归地做这件事。我的策略是确定头部是否有数据
一个很好的策略，和MASh的建议类似，下面和我的努力。
也许下面的RemveR（）方法将有助于完成您的工作。
在这个例子中，我没有提供尾部递归。下面的方法是我的'传统'，即简单的实现。（最近，我发现我很少使用列表，更喜欢d::向量。）
环境：
Ubuntu 15.10，64位，在较旧的Dell上，
g-5（Ubuntu 5.2.1-23ubuntu1~15.10）5.2.1 20151028
代码：
#include <chrono>
// 'compressed' chrono access --------------vvvvvvv
typedef std::chrono::high_resolution_clock HRClk_t; // std-chrono-hi-res-clk
typedef HRClk_t::time_point Time_t; // std-chrono-hi-res-clk-time-point
typedef std::chrono::milliseconds MS_t; // std-chrono-milliseconds
typedef std::chrono::microseconds US_t; // std-chrono-microseconds
typedef std::chrono::nanoseconds NS_t; // std-chrono-nanoseconds
using namespace std::chrono_literals; // support suffixes like 100ms, 2s, 30us
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cassert>
class Node_t
{
private:
size_t m_id; // node indx
int m_data;
Node_t* m_next;
static size_t M_id;
public:
Node_t() = delete; // disallow default ctor
Node_t(int d) : m_id(++M_id) , m_data(d) , m_next(nullptr) { }
~Node_t() { std::cout << " ~Node_t() " << show() << std::endl; }
void appendR(Node_t* n)
{
if(m_next) m_next->appendR(n); // spin to end of list
else m_next = n; // append to end
}
bool dataMatch(int v) { return (m_data == v); }
Node_t* next() { return (m_next); }
// when m_next->m_data matches v, returns true, else false
bool removeR(int v);
std::string showR()
{
std::string s = show();
if(m_next)
s += m_next->showR(); // spin to end of list
return (s);
}
std::string show()
{
std::stringstream ss;
if (false) ss << "[" << std::to_string(m_id) << "]"; // node indx
if (false) ss << std::to_string(m_id) << ":"; // node indx
ss << std::to_string(m_data) << " ";
return ss.str();
}
size_t size() {
size_t retVal = 1;
if (m_next) { retVal += m_next->size(); } // spin to end of list
return retVal;
}
}; // class Node_t
size_t Node_t::M_id = 0; // unique id for each node
class LinkedList_t
{
private:
Node_t* m_head;
public:
LinkedList_t() : m_head (nullptr) { }
~LinkedList_t() = default;
void append(Node_t* n)
{
assert(n);
if (nullptr == m_head) m_head = n;
else m_head->appendR(n);
}
void removeR(int v);
std::string show()
{
std::string s("ll is empty");
if(m_head)
s = m_head->showR();
return (s);
}
size_t size() {
size_t retVal = 0;
if (m_head) retVal += m_head->size();
return retVal;
}
}; // class LinkedList_t
void LinkedList_t::removeR(int v)
{
if(nullptr == m_head) // empty list check
{
std::cout << "\n empty" << std::endl;
return;
}
if(m_head->dataMatch(v)) // check data at head
{
Node_t* tmp = m_head;
m_head = tmp->next(); // unlink prev head
delete tmp;
removeR(v); // local recursion... node 2 might also contain v
}
// not empty && data at head not v then use node recursion
if(m_head) (void)m_head->removeR(v);
}
bool Node_t::removeR(int v)
{
bool match = false;
if (m_next) match = m_next->removeR(v); // spin to end of list
// during decurse
if(match) // m_next->data matches v
{
Node_t* matchNode = m_next; // node-to-remove
m_next = m_next->m_next; // remove link to node-to-remove
delete matchNode; // remove node
}
// else no remove to do
return (m_data == v); // continue decurse, checking for another match
}
class T516_t
{
private:
LinkedList_t m_ll;
public:
T516_t() = default;
~T516_t() = default;
int exec()
{
show("m_ll.show().1");
std::cout << "\n m_ll.size() = " << m_ll.size() << std::endl;
for(int i=0; i<6; ++i)
{
Node_t* n = new Node_t(i+10); assert(n); // 10..15
m_ll.append(n);
}
for(int i=0; i<6; ++i)
{
Node_t* n = new Node_t(i+10); assert(n); // 10..15
m_ll.append(n);
};
show("m_ll.show().2");
std::cout << "\n m_ll.size() = " << m_ll.size() << std::endl;
show("remove(15)");
m_ll.removeR(15);
show("m_ll.show().3");
show("remove(10)");
m_ll.removeR(10);
show("m_ll.show().z");
for (int i=0; i<6;++i)
{
std::cout << "\n remove(" << i+10 << ") " << std::endl;
m_ll.removeR(i+10);
show("m_ll.show()...");
}
return(0);
}
private:
void show(std::string lbl) {
std::cout << "\n " << lbl
<< " sz:" << m_ll.size()
<< " " << m_ll.show() << std::endl;
}
}; // class T516_t
int main(int , char** )
{
Time_t start_us = HRClk_t::now();
int retVal = -1;
{
T516_t t516;
retVal = t516.exec();
}
auto duration_us = std::chrono::duration_cast<US_t>(HRClk_t::now() - start_us);
std::cout << "\n\n FINI " << duration_us.count() << " us" << std::endl;
return(retVal);
}
结果：
R02: dumy524.cc
rm -f dumy524
g++-5 -m64 -O3 -ggdb -std=c++++14 -Wall -Wextra -Wshadow -Wnon-virtual-dtor -pedantic -Wcast-align -Wcast-qual -Wconversion -Wpointer-arith -Wunused -Woverloaded-virtual -O0 dumy524.cc -o dumy524 -L../../bag -lbag_i686
real 0m1.065s
user 0m0.920s
sys 0m0.100s
m_ll.show().1 sz:0 ll is empty
m_ll.size() = 0
m_ll.show().2 sz:12 10 11 12 13 14 15 10 11 12 13 14 15
m_ll.size() = 12
remove(15) sz:12 10 11 12 13 14 15 10 11 12 13 14 15
~Node_t() 15
~Node_t() 15
m_ll.show().3 sz:10 10 11 12 13 14 10 11 12 13 14
remove(10) sz:10 10 11 12 13 14 10 11 12 13 14
~Node_t() 10
~Node_t() 10
m_ll.show().z sz:8 11 12 13 14 11 12 13 14
remove(10)
m_ll.show()... sz:8 11 12 13 14 11 12 13 14
remove(11)
~Node_t() 11
~Node_t() 11
m_ll.show()... sz:6 12 13 14 12 13 14
remove(12)
~Node_t() 12
~Node_t() 12
m_ll.show()... sz:4 13 14 13 14
remove(13)
~Node_t() 13
~Node_t() 13
m_ll.show()... sz:2 14 14
remove(14)
~Node_t() 14
~Node_t() 14
empty
m_ll.show()... sz:0 ll is empty
remove(15)
empty
m_ll.show()... sz:0 ll is empty
FINI 591 us
笪波鸿
有很多方法可以做到。
我个人遵循一种简单的方法，在调用递归函数之前处理签入头。
if(list->head->data == value)
{
Node* temp = list->head;
list->head = list->head->next;
delete temp;
}
if(list->head != null)
deleteNodeRecursively(list->head,list->head->next,value);
递归函数应该是这样的，
void deleteNodeRecursively(Node* parent, Node* child, int value){
if (child == NULL){ // if null that means end of the list
return;
}
if( child->data == value)
{
parent->next = child->next; // attach the parent with the next of child. Thus removes the child form the list
delete child; // clear the dynamically allocated memory
deleteNodeRecursively(parent,parent->next,value);
}
else
deleteNodeRecursively(child,child->next,value); // move to the next
}
另外，如果可以避免递归，请避免递归。因为如果列表足够长，它将在到达末尾之前消耗您的全部堆栈内存。
类似资料：
-
给定一个链表和一个指定的数据值，我想递归地删除包含所述数据的所有节点。（我已经找到了迭代的方法，但我想这样做）。我已将我的结构定义为： 为了删除，我做了这个助手函数，它（应该）返回指向我删除列表的头节点的指针： 然后我想在我的实际列表中使用它： 但这不起作用。看起来我的助手函数实际上不起作用，但我无法理解。出什么事了？
-
几个月前我学习了递归，现在这一切都很混乱。有一个人可以解释我整个功能是如何正常工作的，但我有点明白它是如何工作的，但我认为有些步骤在我的脑海中并不是很清楚。病人的Thx提前。
-
所以我有一个链接列表，我希望能够删除一个数字的第一次出现， 我正在尝试使用递归，但不幸的是，我最终只能删除列表的头部 我有三个不同的类，一个用于末尾的空列表，另一个类声明这个方法和实际的列表。
-
我正在学习数据结构，并试图理解Java中的链接列表。我的问题是，我有麻烦与删除节点在给定的索引递归。我的目标是得到O（log n），而不是使用循环，最后得到O（n）。 因此，当我试图删除索引2的条目时，它会删除该索引之前的所有数字，但不会删除该索引-因此它会删除[0]和[1]，但不会删除[2]。 例如，在此代码中，删除前的数组填充为：。调用后，它有以下条目： 我只想删除13，这样数组就会像这样：
-
我想递归地删除一个链表。我想到了如何迭代地做到这一点，但我对如何做到这一点很好奇。到目前为止我有： 我定义的地方 如果需要，我可以去掉头部，但我不知道如何去掉身体或尾巴，然后正确地缝合列表，更不用说递归地做了。我该如何进行？为什么这样不行？ 编辑：删除问号并替换为我认为可行的代码。
-
我需要返回带有删除的所有重复元素的链表的头部。我理解这个问题的逻辑，但我在使用递归时变得困惑。 如果我在If条件之前调用函数RemoveDuplicates（head.next）；很好用。但是，如果我交换语句的顺序（rest所有内容都完全相同），如下所示： 代码无法正确解决像'1->1->1->1'这样的测试用例。在后一种情况下，我得到的输出是'1->1'。 我真的想要一些关于我如何更好地理解递归