CPP

c++ swap nodes in a linked list

void swapNodeValues(int node1, int node2) {
  
  //1. count the number of nodes in the list
  Node* temp = head;
  int N = 0;
  while(temp != NULL) {
    N++;
    temp = temp->next;
  }

  //2. check if the swap positions are valid entries
  if(node1 < 1 || node1 > N || node2 < 1 || node2 > N)
    return;

  //3. traverse to the nodes where values to be swapped
  Node* pos1 = head;
  Node* pos2 = head;
  for(int i = 1; i < node1; i++) {
    pos1 = pos1->next;
  }
  for(int i = 1; i < node2; i++) {
    pos2 = pos2->next;
  }

  //4. swap the values of two nodes
  int val = pos1->data;
  pos1->data = pos2->data;
  pos2->data = val;
}

c++ swap nodes in a linked list

/* This program swaps the nodes of linked list rather
than swapping the field from the nodes.*/
#include <bits/stdc++.h>
using namespace std;
 
/* A linked list node */
class Node {
public:
    int data;
    Node* next;
};
 
/* Function to swap nodes x and y in linked list by
changing links */
void swapNodes(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
    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
    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
    Node* temp = currY->next;
    currY->next = currX->next;
    currX->next = temp;
}
 
/* Function to add a node at the beginning of List */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new 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(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
 
/* Driver program to test above function */
int main()
{
    Node* start = NULL;
 
    /* The constructed linked list is:
    1->2->3->4->5->6->7 */
    push(&start, 7);
    push(&start, 6);
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);
 
    cout << "Linked list before calling swapNodes() ";
    printList(start);
 
    swapNodes(&start, 4, 3);
 
    cout << "
Linked list after calling swapNodes() ";
    printList(start);
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

swap two nodes of a linked list

// Java program to swap two given nodes of a linked list
public class Solution {
 
    // Represent a node of the singly linked list
    class Node {
        int data;
        Node next;
 
        public Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }
 
    // Represent the head and tail of the singly linked list
    public Node head = null;
    public Node tail = null;
 
    // addNode() will add a new node to the list
    public void addNode(int data)
    {
        // Create a new node
        Node newNode = new Node(data);
 
        // Checks if the list is empty
        if (head == null) {
            // If list is empty, both head and
            // tail will point to new node
            head = newNode;
            tail = newNode;
        }
        else {
            // newNode will be added after tail such that
            // tail's next will point to newNode
            tail.next = newNode;
            // newNode will become new tail of the list
            tail = newNode;
        }
    }
 
    // swap() will swap the given two nodes
    public void swap(int n1, int n2)
    {
        Node prevNode1 = null, prevNode2 = null,
             node1 = head, node2 = head;
 
        // Checks if list is empty
        if (head == null) {
            return;
        }
 
        // If n1 and n2 are equal, then
        // list will remain the same
        if (n1 == n2)
            return;
 
        // Search for node1
        while (node1 != null && node1.data != n1) {
            prevNode1 = node1;
            node1 = node1.next;
        }
 
        // Search for node2
        while (node2 != null && node2.data != n2) {
            prevNode2 = node2;
            node2 = node2.next;
        }
 
        if (node1 != null && node2 != null) {
 
            // If previous node to node1 is not null then,
            // it will point to node2
            if (prevNode1 != null)
                prevNode1.next = node2;
            else
                head = node2;
 
            // If previous node to node2 is not null then,
            // it will point to node1
            if (prevNode2 != null)
                prevNode2.next = node1;
            else
                head = node1;
 
            // Swaps the next nodes of node1 and node2
            Node temp = node1.next;
            node1.next = node2.next;
            node2.next = temp;
        }
        else {
            System.out.println("Swapping is not possible");
        }
    }
 
    // display() will display all the
    // nodes present in the list
    public void display()
    {
        // Node current will point to head
        Node current = head;
 
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        while (current != null) {
            // Prints each node by incrementing pointer
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
 
    public static void main(String[] args)
    {
 
        Solution sList = new Solution();
 
        // Add nodes to the list
        sList.addNode(1);
        sList.addNode(2);
        sList.addNode(3);
        sList.addNode(4);
        sList.addNode(5);
        sList.addNode(6);
        sList.addNode(7);
 
        System.out.println("Original list: ");
        sList.display();
 
        // Swaps the node 2 with node 5
        sList.swap(6, 1);
 
        System.out.println("List after swapping nodes: ");
        sList.display();
    }
}

Swap given nodes in a Doubly Linked List without modifying data

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Link list Node Class
class Node {
public:
    int data;
    Node* prev;
    Node* next;
 
    // Constructor function
    Node(int data)
    {
        this->data = data;
        this->prev = NULL;
        this->next = NULL;
    }
};
 
// Function to print linked list
void print(Node* head)
{
    Node* temp = head;
 
    // Iterate until node is NOT NULL
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}
 
// Function to push a node in DLL
void push(Node*& head, Node*& tail,
          int item)
{
 
    // DLL is empty
    if (tail == NULL) {
 
        Node* temp = new Node(item);
        tail = temp;
        head = temp;
    }
 
    // DLL is not empty
    else {
        Node* temp = new Node(item);
        tail->next = temp;
        temp->prev = tail;
        tail = temp;
    }
}
 
// Function to find the nodes
// which have to be swapped
pair<Node*, Node*> find(Node*& head,
                        int x, int y)
{
    Node* N1 = NULL;
    Node* N2 = NULL;
    Node* temp = head;
 
    // Traversing the list
    while (temp != NULL) {
        if (temp->data == x)
            N1 = temp;
        else if (temp->data == y)
            N2 = temp;
        temp = temp->next;
    }
    return make_pair(N1, N2);
}
 
// Function to swap the nodes
// consisting of x and y
void swap(Node*& head, Node*& tail,
          int x, int y)
{
 
    // Edge Cases
    if (head == NULL || head->next == NULL
        || x == y)
        return;
 
    // Finding the Nodes
    pair<Node*, Node*> p = find(head, x, y);
 
    Node* Node1 = p.first;
    Node* Node2 = p.second;
 
    if (Node1 == head)
        head = Node2;
    else if (Node2 == head)
        head = Node1;
    if (Node1 == tail)
        tail = Node2;
    else if (Node2 == tail)
        tail = Node1;
 
    // Swapping Node1 and Node2
    Node* temp;
    temp = Node1->next;
    Node1->next = Node2->next;
    Node2->next = temp;
 
    if (Node1->next != NULL)
        Node1->next->prev = Node1;
    if (Node2->next != NULL)
        Node2->next->prev = Node2;
 
    temp = Node1->prev;
    Node1->prev = Node2->prev;
    Node2->prev = temp;
 
    if (Node1->prev != NULL)
        Node1->prev->next = Node1;
    if (Node2->prev != NULL)
        Node2->prev->next = Node2;
}
 
// Driver Code
int main()
{
 
    Node* head = NULL;
    Node* tail = NULL;
 
    push(head, tail, 1);
    push(head, tail, 8);
    push(head, tail, 7);
    push(head, tail, 9);
    push(head, tail, 4);
 
    int X = 1, Y = 4;
 
    cout << "Before Swapping: ";
    print(head);
 
    swap(head, tail, X, Y);
    cout << "After Swapping: ";
    print(head);
 
    return 0;
}