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 ListNode
Here 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