Complete the following c++ function: Problem 4 (25pt) Suppose that a singly-link
ID: 3700841 • Letter: C
Question
Complete the following c++ function:
Problem 4 (25pt) Suppose that a singly-linked list is defined as in Problem 3. Implement recursive function interleave that will merge two singly-linked lists L1 and L2 such that the first element from L1 is followed by the first element from L2, the second element from L1 is followed by the second element from L2, and so on. The merging should terminate as soon as the end of one of the input lists is reached. For example, if L1- (ao, ai , a2, ??, a4) and L2-(bo, bi , b) then the merged sequence should be (ao, bo, a, b, a2, b). Your function should be specified as //L1 stores head of L1, L2 stores head of L2 // Function should return head of the merged list template snode-T interleave(snodeExplanation / Answer
complete function:-
//add a function:
void MoveNode(snode<T>** destRef, snode<T>** sourceRef)
{
snode<T>* newNode = *sourceRef;
assert(newNode != NULL);
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
template <typename T>
snode<T>* interleave(snode<T>* L1, snode<T> * L2){
snode<T>* dummy;
snode<T>* tail = &dummy;
dummy.next = NULL;
while (1)
{
if (L1 == NULL)
{
break;
}
MoveNode(&(tail->next), &L1);
MoveNode(&(tail->next), &L2);
L1=L1->next;
L2=L2->next;
tail = tail->next;
}
return(dummy.next);
}