I was doing a leetcode problem and realized I've never passed a linked list to a function before. So, now I'm attempting to implement a linked list using a class that inherits the structure of a linked list. In my main code I'm attempting to pass a ListNode* type to the function add2numbers that is a replica of the leetcode problem along with the structure. From what I see in the watch window, Num_List *list; contains all the data of the linked list I just made but I can't pass that due to a type complaint because its from the Num_List class.
#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;
}
Above I tried to some wonky type conversion but no luck. I'd like it to accept the linked list but I'm pretty sure I didn't actually pass it the Linked list but just a reference that happens to hold the same data. Its like I'm passing a phantom list right now because I haven't actually set anything to represent the linked list like linked_list= list1;
Glad to see someone make a proper linked list class for this. For a while, I thought I was the only one!
In production code, you should prefer to use std::list or std::forward_list for your linked lists. It is unfortunate that LeetCode does not do that in its problems. Given that LeetCode does not, writing a custom linked list class is the next best thing.
Using inheritance, however, is the wrong idea. Public inheritance often implies an "is-a" relationship, and that does not exist here. A List is not a special type of ListNode.
So, the design below does not use inheritance. In addition, it stores pointer head within the List class as a member variable. You can see the complete code for class LeetCode_ForwardList below, but the important thing for your question are these two functions:
class LeetCode_ForwardList
{
ListNode* head{ nullptr };
public:
// ...
ListNode* get() const noexcept {
return head; // Retain ownership.
}
ListNode* release() noexcept {
return std::exchange(head, nullptr); // Relinquish ownership.
}
}
Member functions get and release are modeled after std::unique_ptr. They both return the value of pointer head, but get retains ownership of the list (and the responsibility to delete the list nodes when the lifetime of the LeetCode_ForwardList object ends). Function release relinquishes ownership, and sets pointer head to nullptr.
Although the listing below omits source code for function addTwoNumbers, the solution I wrote uses function get. Thus, the caller in my program retains ownership of the lists. Depending how you code addTwoNumbers in your program, you can use either get or release.
Here is the driver that uses function get. Function solve is where addTwoNumbers is invoked.
// LeetCode_0002_Add_Two_Numbers.ixx
export module LeetCode_0002_Add_Two_Numbers;
import std;
import LeetCode_ForwardList; // see below
//======================================================================
// to_int
//======================================================================
int to_int(LeetCode_ForwardList const& list) noexcept
{
int i{}, place{ 1 };
auto node{ list.get() };
while (node) {
i += place * node->value;
place *= 10;
node = node->next;
}
return i;
}
//======================================================================
// to_list
//======================================================================
LeetCode_ForwardList to_list(int i)
{
// Precondition established by caller: i >= 0
LeetCode_ForwardList list;
list.push_front(i % 10);
auto tail{ list.get() };
for (i /= 10; i != 0; i /= 10) {
tail->next = new ListNode(i % 10);
tail = tail->next;
}
return list;
}
//======================================================================
// Solution
// This class is supplied by LeetCode, as part of its problem
// specification.
//
// Depending how you code your solution, it may not be necessary to
// declare a `LeetCode_ForwardList` object in function `addTwoNumbers`.
// In case your solution does, however, you should use function `release`
// to return the `ListNode*` required by function `addTwoNumbers`.
//
// For example:
//
// LeetCode_ForwardList sum;
// ...
// return sum.release(); // Pass ownership to the caller.
//
// In case your function does not use a `LeetCode_ForwardList` object,
// you will have to implement some other mechanism to catch any
// `std::bad_alloc` objects that are thrown by your function, and then
// delete any list nodes that were allocated prior to the `bad_alloc`.
// Otherwise, your function may leak memory.
//
// See functions `to_int` and `to_list` (above) to get an idea of how
// to program with `LeetCode_ForwardList`. They don't leak.
//======================================================================
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return {}; // Stub function returns `nullptr`
}
};
//======================================================================
// solve
//======================================================================
void solve(
std::string_view heading,
std::vector<int> v1,
std::vector<int> v2)
{
Solution s;
LeetCode_ForwardList 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
LeetCode_ForwardList and ListNodeHere is the code for the list classes. Note the constructor that accepts a vector argument. That's where the lists are constructed for the examples in function solve (above).
// LeetCode_ForwardList.ixx
export module LeetCode_ForwardList;
import std;
//======================================================================
// ListNode
//
// This struct is specified by certain problems at LeetCode, including
// these:
//
// - LeetCode 2. Add Two Numbers
// - LeetCode 234. Palindrome Linked List
//
// In a proper design for a "forward linked list," `ListNode` would be
// coded as a nested struct, within the list class itself, rather than
// as a stand-alone struct. LeetCode, however, does not allow that
// option. Its solution specifications require a stand-alone struct.
//
// Worse yet, LeetCode does not define a list class to manage the nodes
// of a linked list. Instead, it passes naked `ListNode` pointers, and
// treats them as lists. No effort is made to implement any of the
// special functions required by the "Rule of Five."
//======================================================================
export struct ListNode {
int value{};
ListNode* next{ nullptr };
ListNode(
int const value = 0,
ListNode* const next = nullptr)
: value{ value }
, next{ next }
{}
};
//======================================================================
// LeetCode_ForwardList
//
// This class implements a forward linked list where each node holds an
// integer value. It is a light-weight class intended for use only in
// certain LeetCode problems that use the `ListNode` struct defined
// above. As such, it is not intended to be an industrial-strength
// library class.
//
// That said, this class does implement the "Rule of Five" (or, rather,
// the "Rule of Four (and a half)", which, effectively, is the same
// thing).
//======================================================================
export class LeetCode_ForwardList
{
ListNode* head{ nullptr };
public:
LeetCode_ForwardList() = default;
LeetCode_ForwardList(ListNode* const head) : head{ head } {}
LeetCode_ForwardList(std::vector<int> const& vec)
: head{ nullptr }
{
try { push_front(vec); }
catch (std::bad_alloc const&) { clear(); throw; }
}
// "Rule of Four (and a half)"
~LeetCode_ForwardList() noexcept {
clear();
}
LeetCode_ForwardList(LeetCode_ForwardList const& that)
: head{ nullptr }
{
if (that.head) {
push_front(that.head->value); // Nothing leaks if this throws.
auto tail{ this->head };
auto node{ that.head->next };
while (node) {
try { tail->next = new ListNode(node->value); }
catch (std::bad_alloc const&) { clear(); throw; } // Prevent leaks.
tail = tail->next;
node = node->next;
}
}
}
LeetCode_ForwardList(LeetCode_ForwardList&& that) noexcept
: head{ std::exchange(that.head, nullptr) }
{}
LeetCode_ForwardList& operator= (LeetCode_ForwardList that) noexcept {
swap(that);
return *this;
}
void swap(LeetCode_ForwardList& that) noexcept {
using std::swap;
swap(this->head, that.head);
}
friend void swap(LeetCode_ForwardList& a, LeetCode_ForwardList& b) noexcept {
a.swap(b);
}
// Other member functions
void clear() noexcept {
while (head)
pop_front();
}
bool empty() const noexcept {
return head == nullptr;
}
ListNode* get() const noexcept {
return head; // Retain ownership.
}
void pop_front() noexcept {
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== (LeetCode_ForwardList const& that) const noexcept {
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!= (LeetCode_ForwardList const& that) const noexcept {
// This function can be omitted in C++20 and later.
return !(*this == that);
}
friend std::ostream& operator<< (std::ostream& ost, LeetCode_ForwardList 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;
}
};
// end file: LeetCode_ForwardList.ixx