Chapter 3, Problem 10C

Algorithm to swap two nodes “x” and “y” in a singly linked list:

//Swapping in singly Linked List

void swappingNodes(Node **head, Node* x, Node* y)

{

//if both nodes are same

if (x == y) return;

// Search for y (keep track of previous of node y and Current node y )

Node *prevY = NULL, *currentY = *head;

while (currentY && currentY!= y)

{

prevY = currentY;

currentY = currentY->next;

}

// Search for x (keep track of previous of node x and Current node x )

Node *prevX = NULL, *currentX = *head;

while (currentX && currentX != x)

{

prevX = currentX;

currentX = currentX->next;

}

// If either x or y is not present in the list

if (currentX == NULL || currentY == NULL)

    return;

// If x is not head of linked list

if (prevX != NULL)

    prevX->next = currentY;

// Else make y as new head

else

    *head = currentY;

// If y is not head of linked list

if (prevY != NULL)

    prevY->next = currentX;

// Else make x as new head

else

    *head = currentX;

// Swap next pointers

Node *temp = currentY->next;

currentY->next = currentX->next;

currentX->next = temp;

}

Explanation:

The above algorithm is used to swap two nodes of a single linked list...

Algorithm to swap two nodes “x” and “y” in a doubly linked list:

//swapping nodes in doubly linked list

void swapingNodes(struct Node* x, struct Node* y)

{

if ( x->prev != NULL)

{

    x->prev->next = y;

}

Else

{

    head = y;

}

if ( y->next !=NULL)

{

    y->next->prev = x;

}

//swapping pointers

x->next = y->next;

y->p...

Algorithm that takes more time:

The singly linked list takes more time than doubly...