C++ Consider the following code: // Linked Lists: SWAP consecutive nodes struct
ID: 3908378 • Letter: C
Question
C++
Consider the following code: // Linked Lists: SWAP consecutive nodes struct Data { int number; char ch; }; struct ListNode { Data data; struct ListNode *next; }; Assume that a linked list has been created and head points to a sentinel node. A sentinel node is an empty data node in the beginning of the list. It sometimes holds a sentinel value. The use of sentinel nodes is a popular trick to simplify the insert, delete, and other operations, such as swap: without a sentinel node we would have to address the special case of swapping the first two nodes. You may also assume that the list is not empty. The data in the sentinel node is -9999. Write a function named swapNodes that is passed the pointer to the sentinel node and a target node number and swaps two consecutive nodes in the list, if possible. The function returns false in this case, true otherwise. A calling statement for this function is given below: bool swapped = swapNodes(head, target); For instance, if the list has 5 nodes (the sentinel node does not count): {-9999, 10, 20, 30, 40, 50}, and the target node number is 1, the first two data nodes will be swapped. The list after processing will contain:{-9999, 20, 10, 30, 40, 50}.
Explanation / Answer
/* C program to pairwise swap elements in a given linked list */
#include<stdio.h>
#include<stdlib.h>
struct Data { int number; char ch; };
/* A linked list node */
struct Node
{
Data data;
struct Node *next;
};
/*Function to swap two integers at addresses a and b */
void swap(int *a, int *b);
/* Function to pairwise swap elements of a linked list */
bool swapNodes(struct Node *head, int target)
{
struct Node *temp = head;
int x=0;
/* Traverse further only if there are at-least two nodes left */
if(temp != NULL && temp->next != NULL && temp->next->next != NULL){
while (temp != NULL && temp->next != NULL && temp->next->next != NULL)
{
x++;//for indexing purpose.
if(x>=target){
/* Swap data of node with its next node's data */
swap(&temp->next->data.number, &temp->next->next->data.number);
/* Move temp by 2 for the next pair */
temp = temp->next->next;
}else
temp = temp->next;
}
return true;
}else{
return false;
}
}
/* UTILITY FUNCTIONS */
/* Function to swap two integers */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Function to add a node at the begining of Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data.number = new_data;
/* link the old list off the new node.nu*/
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node->data.number);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
struct Node *start = NULL;
/* The constructed linked list is:
-9999, 10, 20, 30, 40, 50 */
push(&start, 50);
push(&start, 40);
push(&start, 30);
push(&start, 20);
push(&start, 10);
push(&start, -9999);
printf("Linked list before calling swapNodes() ");
printList(start);
bool isSwaped = swapNodes(start,1);
printf(" Function returns - %s", isSwaped?"true":"false");
printf(" Linked list after calling swapNodes() ");
printList(start);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.