This means that the originally even-valued nodes should be retained as part of the resulting list. Destroy ONLY nodes that are originally odd-valued. Create new nodes and copy data between nodes ONLY when duplicating originally even-valued nodes. Only ONE new node should be created for each originally even-valued node. Creating pointer-to-node's (to provide temporary storage for node addresses) does not constitute creating new nodes or copying of items. NOT make any temporary copies of any of the data items (using any kind of data structures including but not limited to arrays, linked lists and trees). This means that the algorithm should largely involve the manipulation of pointers. Function must be iterative (NOT recursive) - use only looping construct(s), without the function calling itself (directly or indirectly). Function should not call any other functions to help in performing the task.
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
//
/*NOT destroy any of the originally even-valued node.
This means that the originally even-valued nodes should be retained as part of the resulting list.
Destroy ONLY nodes that are originally odd-valued.
Create new nodes and copy data between nodes ONLY when duplicating originally even-valued nodes.
Only ONE new node should be created for each originally even-valued node.
Creating pointer-to-node's (to provide temporary storage for node addresses) does not constitute creating new nodes or copying of items.
NOT make any temporary copies of any of the data items (using any kind of data structures including but not limited to arrays, linked lists and trees).
This means that the algorithm should largely involve the manipulation of pointers.
Function must be iterative (NOT recursive) - use only looping construct(s), without the function calling itself (directly or indirectly).
Function should not call any other functions to help in performing the task.
bool DelOddCopEven(Node* headPtr)
{
}
int FindListLength(Node* headPtr)
{
int length = 0;
while (headPtr != 0)
{
++length;
headPtr = headPtr->link;
}
return length;
}
bool IsSortedUp(Node* headPtr)
{
if (headPtr == 0 || headPtr->link == 0) // empty or 1-node
return true;
while (headPtr->link != 0) // not at last node
{
if (headPtr->link->data < headPtr->data)
return false;
headPtr = headPtr->link;
}
return true;
}
void InsertAsHead(Node*& headPtr, int value)
{
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = headPtr;
headPtr = newNodePtr;
}
void InsertAsTail(Node*& headPtr, int value)
{
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = 0;
if (headPtr == 0)
headPtr = newNodePtr;
else
{
Node *cursor = headPtr;
while (cursor->link != 0) // not at last node
cursor = cursor->link;
cursor->link = newNodePtr;
}
}
void InsertSortedUp(Node*& headPtr, int value)
{
Node *precursor = 0,
*cursor = headPtr;
while (cursor != 0 && cursor->data < value)
{
precursor = cursor;
cursor = cursor->link;
}
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = cursor;
if (cursor == headPtr)
headPtr = newNodePtr;
else
precursor->link = newNodePtr;
///////////////////////////////////////////////////////////
/* using-only-cursor (no precursor) version
Node *newNodePtr = new Node;
newNodePtr->data = value;
//newNodePtr->link = 0;
//if (headPtr == 0)
// headPtr = newNodePtr;
//else if (headPtr->data >= value)
//{
// newNodePtr->link = headPtr;
// headPtr = newNodePtr;
//}
if (headPtr == 0 || headPtr->data >= value)
{
newNodePtr->link = headPtr;
headPtr = newNodePtr;
}
//else if (headPtr->link == 0)
// head->link = newNodePtr;
else
{
Node *cursor = headPtr;
while (cursor->link != 0 && cursor->link->data < value)
cursor = cursor->link;
//if (cursor->link != 0)
// newNodePtr->link = cursor->link;
newNodePtr->link = cursor->link;
cursor->link = newNodePtr;
}
////////////////// commented lines removed //////////////////
Node *newNodePtr = new Node;
newNodePtr->data = value;
if (headPtr == 0 || headPtr->data >= value)
{
newNodePtr->link = headPtr;
headPtr = newNodePtr;
}
else
{
Node *cursor = headPtr;
while (cursor->link != 0 && cursor->link->data < value)
cursor = cursor->link;
newNodePtr->link = cursor->link;
cursor->link = newNodePtr;
}
*/
///////////////////////////////////////////////////////////
}
bool DelFirstTargetNode(Node*& headPtr, int target)
{
Node *precursor = 0,
*cursor = headPtr;
while (cursor != 0 && cursor->data != target)
{
precursor = cursor;
cursor = cursor->link;
}
if (cursor == 0)
{
cout << target << " not found." << endl;
return false;
}
if (cursor == headPtr) //OR precursor == 0
headPtr = headPtr->link;
else
precursor->link = cursor->link;
delete cursor;
return true;
}
bool DelNodeBefore1stMatch(Node*& headPtr, int target)
{
if (headPtr == 0 || headPtr->link == 0 || headPtr->data == target) return false;
Node *cur = headPtr->link, *pre = headPtr, *prepre = 0;
while (cur != 0 && cur->data != target)
{
prepre = pre;
pre = cur;
cur = cur->link;
}
if (cur == 0) return false;
if (cur == headPtr->link)
{
headPtr = cur;
delete pre;
}
else
{
prepre->link = cur;
delete pre;
}
return true;
}
void ShowAll(ostream& outs, Node* headPtr)
{
while (headPtr != 0)
{
outs << headPtr->data << " ";
headPtr = headPtr->link;
}
outs << endl;
}
Step by step
Solved in 4 steps with 2 images
