Single linked lists merge
What is the best way to merge 2 single linked list (list1 and list 2) into a 3rd list (list3). The lists are of type INT. These single linked list are not arrays and are created with a Struct and pointers.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
If the lists were sorted you need something like that:
struct Node
{
int data;
Node* pNext;
Node(int d) : data(d), pNext(NULL) {}
~Node() { delete pNext; }
};
class SList
{
Node* pHead;
Node* pLast;
public:
SList() : pHead(NULL), pLast(NULL) {}
~SList() { delete pHead; }
void Add(int d)
{
Node* p = new Node(d);
if (pHead == NULL)
pHead = pLast = p;
else
{
pLast->pNext = p;
pLast = p;
}
}
SList(const SList& list1, const SList2& list2)
{
Node* p1 = list.pHead;
Node* p2 = list2.pHead;
while (p1 != NULL || p2 != NULL)
{
if (p1 == NULL && p2 == NULL)
{
if (p1->data < p2->data)
{
Add(p1->data);
p1 = p1->pNext;
}
else
{
Add(p2->data);
p2 = p2->pNext;
}
}
else if (p1 != NULL)
{
Add(p1->data);
p1 = p1->pNext;
}
else
{
Add(p2->data);
p2 = p2->pNext;
}
}
}
};
Regards, Alex
struct Node
{
int data;
Node* pNext;
Node(int d) : data(d), pNext(NULL) {}
~Node() { delete pNext; }
};
class SList
{
Node* pHead;
Node* pLast;
public:
SList() : pHead(NULL), pLast(NULL) {}
~SList() { delete pHead; }
void Add(int d)
{
Node* p = new Node(d);
if (pHead == NULL)
pHead = pLast = p;
else
{
pLast->pNext = p;
pLast = p;
}
}
SList(const SList& list1, const SList2& list2)
{
Node* p1 = list.pHead;
Node* p2 = list2.pHead;
while (p1 != NULL || p2 != NULL)
{
if (p1 == NULL && p2 == NULL)
{
if (p1->data < p2->data)
{
Add(p1->data);
p1 = p1->pNext;
}
else
{
Add(p2->data);
p2 = p2->pNext;
}
}
else if (p1 != NULL)
{
Add(p1->data);
p1 = p1->pNext;
}
else
{
Add(p2->data);
p2 = p2->pNext;
}
}
}
};
Regards, Alex
struct ListEntry {
int data;
struct ListEntry* pNext;
};
ListEntry* List1 = GetHeadOfList1();
ListEntry* List2 = GetHeadOfList2();
// go to the end of List1
while ( List1->pNext != NULL) List1 = List1->pNext;
// Set 'pNext' to the head of list2 to join them
List1->pNext = List2;