Assume the following declaration for the implementation of a dynamic linked list
ID: 3700457 • Letter: A
Question
Assume the following declaration for the implementation of a dynamic linked list is given struct ListNode int val, struct ListNode tnext Write a function MovePosition that takes one list, a node value and a position value. Then it moves the given node value to n positions forward. For example, if the function call is as follows: MovePosition (myList, 6, 2) This means the node value 6 needs to be moved two positions forward, therefore if the input list is as follows: mvList 6 91020 NULL After the function call, the resulting list will be as follows: mvList 910620 NULL Please note if the calculated position is longer than the length of the list then you will just add the node to the end of the list. In addition, if the given node value is not in the list, then the list will not be changed.Explanation / Answer
void MovePosition(struct ListNode *myList, int node, int position)
{
if( position == 0 )
return;
// if the list is empty
if( !myList )
return;
// point trav to head of the list
struct ListNode *trav = myList;
// point to the previous node
struct ListNode *pre = NULL;
// iterate through the list to point trav to the requird node
// which is to be moved
while( trav )
{
// if required node is found
if( trav->val == node )
break;
// point pre to current node
pre = trav;
// move to next node
trav = trav->next;
}
// if the list has ended
if( !trav )
return;
// point x to the node which is to be moved
struct ListNode *x = trav;
// if node to be moved is head
if( trav == myList )
{
// make second node as th new head
head = trav->next;
for( i = 1 ; i < position ; i++ )
{
// if position is greater the the number of nodes
// and now the lits ended
if( !trav )
return;
trav = trav->next;
}
// add the node after moving
x->next = trav->next;
trav->next = x;
return;
}
for( i = 1 ; i < position ; i++ )
{
// if position is greater the the number of nodes
// and now the lits ended
if( !trav )
return;
trav = trav->next;
}
// remove x from the original position
pre->next = x->next;
// add the node after moving
x->next = trav->next;
trav->next = x;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.