C++

Forum

 
 
linked list union operation function issue

djhyun0001 (21)
Hi,

I am having a problem with my union operation function. at the end of the function, I am supposed to clear the both parameter lists. but, at the end of the function, the left list contains the right list become the union of the two list and deleting the right after left crash my program with deleting unallocated pointer. I do have result pointer, that contains the union of the two lists and I use that. Can anyone help me where I am doing wrong to linking right list's head as the left list's last node's next?

Thanks,
Ryan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
//----------------------------------------------------------------------------
// merge
// Takes 2 sorted lists and merge into one long sorted list
// @pre   : head point to the first node in list
// @post  : current list becomes the merged list of the two parameter lists and
//          two parameter list becomes empty unless one is also the current
//          object
// @param : left, list to be merged
// @param : right, list to be merged
// @return: none
template <typename T>
void List<T>::merge(List& left, List& right)  {
    
    // handle when either one of the lists is NULL
    if (right.head == NULL)  {
        if (&left != this)  {
            makeEmpty();
            copyList(left);
        }
    }
    else if (left.head == NULL)  {
        if (&right != this)  {
            makeEmpty();
            copyList(right);
        }
    }
    else if (right.head == NULL && left.head == NULL)  {
        makeEmpty();
    }
    else {
        Node* result;
        Node* current;
        
        Node* leftHead = left.head;
        Node* rightHead = right.head;
        
        // assign the node with smallest data as the head
        if (*leftHead->data < *rightHead->data)  {
            result = leftHead;
            leftHead = leftHead->next;
        }
        else  {
            result = rightHead;
            rightHead = rightHead->next;
        }
        
        current = result;
        
        // place the node in correct location, order by node->data
        while (leftHead != NULL && rightHead != NULL)  {
            if (*leftHead->data < *rightHead->data)  {
                result->next = leftHead;
                leftHead = leftHead->next;
            }
            else  {
                result->next = rightHead;
                rightHead = rightHead->next;
            }
            result = result->next;
        }
        
        // finish merge by linking the reast of the nodes
        if (leftHead != NULL) {
            result->next = leftHead;
        }
        if (rightHead != NULL)  {
            result->next = rightHead;
        }
        
        head = current;
        if (&left != this)  {
            left.makeEmpty();
        }
        if (&right != this)  {
            right.makeEmpty();
        }
        size = left.size + right.size;
    }
}
Last edited on
ne555 (10692)
> I am supposed to clear the both parameter lists.
¿where are you doing that?
In the simple case where `right' is empty you do copyList(left);
You could simply modify the `head' instead of doing a deep copy of the whole list. (if `copyList()' does not do a deep copy, then its name is terrible)


> left.makeEmpty();
you never copied the nodes, you simply relink them. Destroying all the nodes in `left' would destroy them too in your union, so you would have an invalid access and a double delete.
You simply need to set the `head' to null.

Also, I shouldn't have to guess what your functions do. Post a minimal example that reproduces your problem.
djhyun0001 (21)
thank you for the explanation. I think I know what I am doing wrong. I was supposed to re-link the new lists to the current list, instead of making deep copy and deleting the parameter lists.
Topic archived. No new replies allowed.