QUESTION
Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields.\n\nIt may be assumed that all keys in linked list are distinct.\n\nExamples:\n\nInput: 10->15->12->13->20->14, x = 12, y = 20\nOutput: 10->15->20->13->12->14\n\nInput: 10->15->12->13->20->14, x = 10, y = 20\nOutput: 20->15->12->13->10->14.
“TESTCASE_1”: “6\n10 15 12 13 20 14\n12 20\n###—###SEPERATOR—###—\n10 15 20 13 12 14”, “TESTCASE_2”: “6\n10 15 12 13 20 14\n10 20\n###—###SEPERATOR—###—\n20 15 12 13 10 14”, “TESTCASE_3”: “6\n10 15 12 13 20 14\n12 13\n###—###SEPERATOR—###—\n10 15 13 12 20 14”, “TESTCASE_4”: “5\n1 2 9 47 5\n2 5\n###—###SEPERATOR—###—\n1 5 9 47 2”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
/* This program swaps the nodes of linked list rather
than swapping the field from the nodes.*/
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */
struct Node
{
int data;
struct Node *next;
};
/* Function to swap nodes x and y in linked list by
changing links */
void swapNodes(struct Node **head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return;
// Search for x (keep track of prevX and CurrX
struct Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x)
{
prevX = currX;
currX = currX->next;
}
// Search for y (keep track of prevY and CurrY
struct Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y)
{
prevY = currY;
currY = currY->next;
}
// If either x or y is not present, nothing to do
if (currX == NULL || currY == NULL)
return;
// If x is not head of linked list
if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head
*head_ref = currY;
// If y is not head of linked list
if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head
*head_ref = currX;
// Swap next pointers
struct Node *temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}
/* Function to add a node at the begining of 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 = new_data;
/* link the old list off the new node */
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);
node = node->next;
}
}
/* Druver program to test above function */
int main()
{
struct Node *start = NULL;
int n,i,p,q;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=n-1;i>=0;i--)
push(&start,arr[i]);
scanf("%d",&p);
scanf("%d",&q);
swapNodes(&start, p, q);
printList(start);
return 0;
}