I have created a singly linked list using structure. The structure holds an integer and a struct pointer next
. I am sorting the list in ascending order. I am passing the head
pointer to a sorting function. The sorting algorithm is working fine but the change is not reflected when I pass the same head
to a display function after sorting. I have also tried using pointer-to-pointer, if that's a recommended solution. Following is a sample code of my program which reproduces the same bug:-
#include<iostream>
class List
{
public:
struct ListNode
{
int Number;
ListNode *next;
}*head;
int TotalNodes;
List()
{
head = NULL;
TotalNodes = 0;
}
void CreateList(int Number)
{
ListNode *newNode, *nodePtr;
newNode = new ListNode;
newNode->Number = Number;
newNode->next = NULL;
++TotalNodes;
if(!head)
{
head = newNode;
}
else
{
nodePtr = head;
while(nodePtr->next) nodePtr = nodePtr->next;
nodePtr->next = newNode;
}
}
void SortList(ListNode *HEAD, int NODECOUNT)
{
int i, Passes = (((NODECOUNT * NODECOUNT) + NODECOUNT) / 2);
ListNode *nodePtr, *lastNode, *lastNodePREV;
for(i=0; i <= Passes; i++)
{
lastNode = HEAD;
nodePtr = lastNode->next;
while(nodePtr->next && lastNode->Number < nodePtr->Number)
{
lastNodePREV = lastNode;
lastNode = lastNode->next;
nodePtr = nodePtr->next;
}
if(lastNode == HEAD)
{
HEAD->next = nodePtr->next;
nodePtr->next = HEAD;
HEAD = nodePtr;
}
else
{
lastNodePREV->next = nodePtr;
lastNode->next = nodePtr->next;
nodePtr->next = lastNode;
}
}
nodePtr = HEAD;
while(nodePtr)
{
std::cout<<" "<<nodePtr->Number;
nodePtr = nodePtr->next;
}
}
void Display(ListNode *HEAD)
{
ListNode *nodePtr;
nodePtr = HEAD;
while(nodePtr)
{
std::cout<<" "<<nodePtr->Number;
nodePtr = nodePtr->next;
}
}
};
int main()
{
List list;
for(int i=10; i >= 0; i--)
{
list.CreateList(i);
}
list.Display(list.head); //before sorting
std::cout<<"\n\n";
list.SortList(list.head, list.TotalNodes);
std::cout<<"\n\n";
list.Display(list.head); //after sorting
return 0;
}
Output of the above program:-
10 9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9 10
10
I think this has something to do with sorting function creating a copy of the list but then what do I do to edit the same list itself?
Thank you.
PS:- I had also tried returning the pointer but then I had got the error about not being able to convert from ListNode*
to List*
for the function:-
ListNode* List::SortList(...)
{
....
....
return HEAD;
}
called in main()
as
list.head = list.SortList(...);
PPS:- The solution to this problem is simply using *&HEAD
instead of *HEAD
in the arguments of function Sortlist()
PPPS:- I want to clarify one more thing that I am using pass-by-reference because I am dealing with several linked lists in my actual program. This is just a sample of it.