Linked List of Shared Pointers Causes Unknown Infinite Loop

[eak006]

Hey guys,

I tackled LeetCode problem #82 - Remove Duplicates From Sorted List II:
- https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

The problem is solved and LeetCode accepted my solution as correct. However, I'm having difficulty debugging my driver code in function `main()`. This is pretty much the first time I'm using smart pointers.

The code below runs just fine if you ignore memory management issues. However, in `main()` if you comment out the assignments to variable `ListNode * head` and un-comment out the code that declares variable `std::shared_ptr<ListNode> head` (and also call `head.get()` where appropriate), the code never finishes.

#include <iostream>
#include <memory>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {};
    ListNode(int x) : val(x), next(nullptr) {};
    ListNode(int x, ListNode *next) : val(x), next(next) {};
};

class Solution
{
    public:
        ListNode * deleteDuplicates(ListNode * head)
        {
            std::shared_ptr<ListNode> shared_pointer = std::make_shared<ListNode>();
        
            // use dummy node; head and tail are initially the same but tail progresses forward
            ListNode * dummy_head = shared_pointer.get();
            ListNode * tail = dummy_head;
            
            int currVal = -101;                                              
            ListNode * prev_node = dummy_head; 
            
            while(head != nullptr) 
            {
                if(head->val == currVal) 
                {                     
                    prev_node->next = head->next;                                  
                    tail = prev_node; 
                }
                else
                { 
                    currVal = head->val; 
                    prev_node = tail; 
                    
                    // include 'head' on this trail
                    tail->next = head;
                    tail = head;
                }
                
                head = head->next; // progress the singly-linked list forward
            }
            
            return dummy_head->next; // return the trail that 'tail' blazed for us.
        };
};

void printLinkedList(ListNode * head)
{
    std::cout << '[';
    while(head != nullptr)
    {
        std::cout << head->val;
        if (head->next != nullptr)
            std::cout << ',';
        head = head->next;
    }
    std::cout << ']' << '\n';
}

int main()
{
    Solution solutionObj;

    ListNode * head = new ListNode(1,new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(4, new ListNode(4, new ListNode(5)))))));
    // std::shared_ptr<ListNode> head = std::make_shared<ListNode>(
    //     1,
    //     std::make_shared<ListNode>(
    //         2,
    //         std::make_shared<ListNode>(
    //             3,
    //             std::make_shared<ListNode>(
    //                 3,
    //                 std::make_shared<ListNode>(
    //                     4,
    //                     std::make_shared<ListNode>(
    //                         4,
    //                         std::make_shared<ListNode>(
    //                             5
    //                         ).get()
    //                     ).get()
    //                 ).get()
    //             ).get()
    //         ).get()
    //     ).get()
    // );
    printLinkedList(solutionObj.deleteDuplicates(head)); // [1,2,5]

    head = new ListNode(1,new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3)))));
    // head = std::make_shared<ListNode>(
    //     1,
    //     std::make_shared<ListNode>(
    //         1,
    //         std::make_shared<ListNode>(
    //             1,
    //             std::make_shared<ListNode>(
    //                 2,
    //                 std::make_shared<ListNode>(
    //                     3
    //                 ).get()
    //             ).get()
    //         ).get()
    //     ).get()
    // ).get();
    printLinkedList(solutionObj.deleteDuplicates(head)); // [2,3]

    return 0;
}

I take it there are still lingering shared pointers in existence that maintain ownership of the `ListNode` objects, but I'm not sure where.

I've noticed that curiously enough, when printing out `head->val` in function `deleteDuplicates`, the value stored inside `dummy_head` is printed first instead of the actual first value of the linked list. That makes no sense to me.

Anyways, I appreciate any insights you can provide to not only debug this mystery but also illuminate my understanding of (smart) pointers.

Thank you

EDIT: I tried the code on the C++ shell, and it seems my solution does in fact traverse the entire input, but then precedes to traverse the numbers 0, 1, 2 forever where 0 is the value stored inside the dummy head node.

[helios]

For any type T, std::make_shared<T>().get() will give you a pointer that's only valid for the execution of the current statement. When the statement containing that subexpression completes, the temporary std::shared_ptr<T> is destructed, which in turn destructs the T (since the temporary shared_ptr was the only extant reference), which in turn invalidates the pointer.
In other words,

int *f(int *p){
    std::cout << *p << std::endl;
    return p;
}

int main(){
    int *p = f(std::make_shared<int>(42).get());
    std::cout << *p << std::endl;
}

The p that f() gets is still valid and the output is defined, but the p that main() gets is invalid as soon as the assignment completes, and by the time main() tries to print *p, p is already invalid and the value that gets printed is undefined.

So, don't do that. If you create smart pointers you need to hold on to them, and if possible avoid calling get(), to prevent these kinds of errors.

[dutch]

deleteDuplicates looks overcomplicated, although it's a little hard to tell with all the "comment" spam.

[kbw]

Code doesn't hang, output is:

[1,2,5]
[2,3]

Dunno what it does. Weird mix of raw and smart pointers.

[eak006]

@helios - Thanks for the insight! Perhaps I should define a destructor for ListNode class that destroys the succeeding trail of pointers once the head pointer is deleted?

@dutch - Good call. I removed most of the comments

@kbw - Sorry for the confusion. My code above runs fine until you un-comment out the linked list of shared pointers in `main()` and pass their respective heads into `deleteDuplicates`. `deleteDuplicates` takes in the head of a sorted linked list and removes all duplicate nodes within that sorted linked list.

[eak006]

This stackoverflow article was helpful:
https://stackoverflow.com/questions/36673391/c-linked-list-using-smart-pointers

[helios]

Perhaps I should define a destructor for ListNode class that destroys the succeeding trail of pointers once the head pointer is deleted?

That would be inadvisable. If the list is long enough you would overflow the stack. The way this is usually handled is by having a LinkedList class that's public, with the Node class being a private implementation detail. LinkedList then manages the nodes' memory and destructs them in a loop in its destructor.