我在做 leetcode 问题时意识到我以前从未将链表传递给函数。因此，现在我尝试使用继承链表结构的类来实现链表。在我的主代码中，我尝试将 ListNode* 类型传递给函数 add2numbers，该函数是 leetcode 问题及其结构的复制品。从我在监视窗口中看到的，Num_List *list;包含我刚刚创建的链表的所有数据，但由于类型投诉，我无法传递它，因为它来自 Num_List 类。
#include<iostream>
#include"List_Node.h"
using namespace std;
int main() {
Num_List *list, *list2;
cout << "List 1" << endl;
cout << "--------" << endl;
list->appendNode(1);
list->appendNode(2);
list->appendNode(3);
list->displayList();
cout << "List 2" << endl;
cout << "--------" << endl;
list2->appendNode(3);
list2->appendNode(2);
list2->appendNode(1);
list2->displayList();
list->addTwoNumbers((ListNode*)list->val, (ListNode*)list2->val);
return 0;
}
#pragma once
#ifndef LIST_NODE_H
#define LIST_NODE_H
struct ListNode {
int val;
struct ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* head;
class Num_List: public ListNode {
private:
public:
//constructor
Num_List() {
head = nullptr;
}
//Destructor
~Num_List();
void appendNode(int);
void insertNode(int);
void deleteNode(int);
void displayList()const;
int addTwoNumbers(ListNode*, ListNode*);
};
#endif
#include"List_Node.h"
#include <iostream>
Num_List::~Num_List()
{
ListNode* nodePtr;// pointer to traverse list
ListNode* nextNode;//pointer to next node
//Position nodePtr at the head of the list
nodePtr = head;
//while nodeptr is no at the end of the list..
while (nodePtr != nullptr) {
//save a pointer to the next node.
nextNode = nodePtr->next;
//delete the current node.
delete nodePtr;
//Position nodePtr a the next node for next loop
nodePtr = nextNode;
}
}
void Num_List::appendNode(int num)
{
ListNode* newNode;
ListNode* nodePtr;
//Allocate a new node and store data there;
newNode = new ListNode;
newNode->val = num;
newNode->next = nullptr;
//If there are no nodes in list
//then make a newNode the head node.
if (!head) {
head = newNode;
}
else {
//Initealize nodePtr to head of the list.
nodePtr = head;
//Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;
//Insert a newNode as the last node ie already points to nullPtr
nodePtr->next = newNode;
}
}
void Num_List::insertNode(int num)
{
ListNode* newNode; // a new node
ListNode* nodePtr;// a pointer to nodes used to traverse list
ListNode* previousNode = nullptr;// the previous node
//Allocate a new node and sotre the num there.
newNode = new ListNode;
newNode->val = num;
//if there are no nodes in the list make newNode the head node;
if (!head)
{
head = newNode;
newNode->next = nullptr;
}
else {//otherwise insert a newNode
//Position nodePtr at the ahead of the list
nodePtr = head;
//Initialize previousNode to nullptr
previousNode = nullptr;
//skip all nodes whose value is less than input value
while (nodePtr != nullptr && nodePtr->val < num) {
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If the new node is to be the 1st in the list,
//insert it before all other nodes.
if (previousNode == nullptr)
{
head = newNode;
newNode->next = nodePtr;
}
else {//otherwise insert after the previous node.
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}void Num_List::deleteNode(int num)
{
ListNode* nodePtr;// a pointer to nodes used to traverse list
ListNode* previousNode = nullptr;// the previous node
//determine if the first node contains the data
if (!head)return;
if (head->val == num) {
nodePtr = head->next;
delete head;
head = nodePtr;
}
else {
//Initialize nodePtr to the head of list
nodePtr = head;
//skip all nodes whose value is not the input value
while (nodePtr != nullptr && nodePtr->val != num) {
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If nodePtr is not at the end of the list,
//link the previous node to the node after nodePtr,
//then delete nodePtr
if (nodePtr) {
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}
using namespace std;
void Num_List::displayList() const
{
ListNode* nodePtr;//pointer to a node int ListNode class
//position nodePtr at the head of the list.
nodePtr = head;
//while nodePtr points to a node, traverse the list
while (nodePtr) {
//display value contained in node
cout << nodePtr->val << endl;
//move to next node
nodePtr = nodePtr->next;
}
}
int Num_List::addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* tail = head;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int dig1 = (l1 != nullptr) ? l1->val : 0;
int dig2 = (l1 != nullptr) ? l1->val : 0;
int sum = dig1 + dig2 + carry;
int digit = sum % 10;
carry = sum / 10;
ListNode* newNode = new ListNode(digit);
tail->next = newNode;
tail = tail->next;
l1 = (l1 != nullptr) ? l1->next : nullptr;
l2 = (l2 != nullptr) ? l2->next : nullptr;
}
ListNode* result = head->next;
delete head;
return (int) result;
}
上面我尝试了一些奇怪的类型转换，但没有成功。我希望它接受链接列表，但我很确定我实际上并没有向它传递链接列表，而只是传递一个恰好包含相同数据的引用。就像我现在正在传递一个幻像列表，因为我实际上没有设置任何东西来表示链接列表，例如 linked_list= list1;
很高兴看到有人为此制作了一个合适的链表类。有一段时间，我以为我是唯一的一个！
然而，使用继承是错误的想法。公共继承通常意味着“is-a”关系，但这里不存在这种关系。 A
ListListNode所以，下面的设计没有使用继承。此外，它将指针
headListListclass List
{
ListNode* head{ nullptr };
public:
// ...
ListNode* release() noexcept {
return std::exchange(head, nullptr); // Relinquish ownership.
}
ListNode* get() const noexcept {
return head; // Retain ownership.
}
}
成员函数
getreleasestd::unique_ptrheadgetListrelease当我调用
addTwoNumbersget这是代码。函数
solveaddTwoNumbers// LeetCode_0002_Add_Two_Numbers.ixx
export module LeetCode_0002_Add_Two_Numbers;
import std;
// struct ListNode...
// class List...
// class Solution...
//======================================================================
// to_int
//======================================================================
int to_int(List const l)
{
int i{}, place{ 1 };
auto node{ l.get() };
while (node)
{
i += place * node->value;
place *= 10;
node = node->next;
}
return i;
}
//======================================================================
// solve
//======================================================================
void solve(
std::string_view heading,
std::vector<int> v1,
std::vector<int> v2)
{
Solution s;
List l1{ v1 }, l2{ v2 }, sum{ s.addTwoNumbers(l1.get(), l2.get()) };
std::cout
<< heading
<< '\n'
<< "\n Input: l1 = " << l1
<< ", l2 = " << l2
<< "\n Output: " << sum
<< "\n Explanation: " << to_int(l1) << " + " << to_int(l2)
<< " = " << to_int(sum) << '.'
<< "\n\n";
}
//======================================================================
// driver
//======================================================================
export bool LeetCode_0002_Add_Two_Numbers() {
std::cout << "LeetCode 2. Add Two Numbers"
"\nhttps://leetcode.com/problems/add-two-numbers/"
"\n\n";
solve("Example 1", { 2, 4, 3 }, { 5, 6, 4 });
solve("Example 2", { 0 }, { 0 });
solve("Example 3", { 9, 9, 9, 9, 9, 9, 9 }, { 9, 9, 9, 9 });
solve("Example 4: Malformed lists", { 10, 12 }, { 34 });
solve("Example 5: Malformed lists", { 1234 }, { 0 });
return true;
}
// end file: LeetCode_0002_Add_Two_Numbers.ixx
ListListNode这是列表类的代码。请注意接受向量参数的构造函数。这就是构建列表的地方。
//======================================================================
// ListNode
//======================================================================
struct ListNode {
int value{};
ListNode* next{ nullptr };
ListNode(
int const value = 0,
ListNode* const next = nullptr)
: value{ value }
, next{ next }
{}
};
//======================================================================
// List
//======================================================================
class List
{
ListNode* head{ nullptr };
public:
List() = default;
List(ListNode* const head) : head{ head } {}
List(std::vector<int> const& vec) { push_front(vec); }
// "Rule of 4 (and a half)"
~List() {
clear();
}
List(List const& that)
: head{ nullptr }
{
if (that.head) {
push_front(that.head->value);
auto tail{ this->head };
auto node{ that.head->next };
while (node) {
tail->next = new ListNode(node->value);
tail = tail->next;
node = node->next;
}
}
}
List(List&& that) noexcept {
this->head = std::exchange(that.head, nullptr);
}
List& operator= (List that) noexcept {
swap(that);
return *this;
}
void swap(List& that) noexcept {
using std::swap;
swap(this->head, that.head);
}
friend void swap(List& a, List& b) noexcept {
a.swap(b);
}
// Other member functions
void clear() {
while (head)
pop_front();
}
bool empty() const {
return head == nullptr;
}
ListNode* get() const noexcept {
return head; // Retain ownership.
}
void pop_front() {
if (head) {
auto node{ head };
head = head->next;
delete node;
}
}
void push_front(std::vector<int> const& vec) {
auto it{ vec.crbegin() };
while (it != vec.crend())
push_front(*it++);
}
void push_front(int const n) {
head = new ListNode(n, head);
}
ListNode* release() noexcept {
return std::exchange(head, nullptr); // Relinquish ownership.
}
bool operator== (List const& that) const {
auto p{ this->head };
auto q{ that.head };
while (p && q)
if (p->value != q->value)
return false;
else
p = p->next, q = q->next;
return !p && !q;
}
bool operator!= (List const& that) const {
return !(*this == that);
}
friend std::ostream& operator<< (std::ostream& ost, List const& list)
{
ost.put('[');
if (auto node{ list.head }; node)
for (;;)
{
ost << node->value;
node = node->next;
if (!node) break;
ost.put(',');
}
ost.put(']');
return ost;
}
};