Swap nodes in a linked list without swapping data

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.