{"id":3757,"date":"2021-08-10T09:27:08","date_gmt":"2021-08-10T09:27:08","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3757"},"modified":"2023-07-27T12:44:36","modified_gmt":"2023-07-27T12:44:36","slug":"swap-nodes-in-a-linked-list-without-swapping-data","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/swap-nodes-in-a-linked-list-without-swapping-data\/","title":{"rendered":"Swap Nodes in a Linked List Without Swapping Data"},"content":{"rendered":"

\"\"<\/p>\n

A linked list is a type of data structure that stores a sequence of elements, each of which points to the next element in the sequence. Linked lists are made up of nodes, each of which contains data as well as a pointer to the next node in the sequence. The first node is referred to as the head node, and the last node is referred to as the tail node. Because they can be dynamically resized, linked lists are commonly used in programming to implement other data structures such as stacks, queues, and hash tables. In this section, we will be discussing how we swap two nodes in linked list<\/p>\n

.<\/p>\n

How to Swap Two Nodes in Linked List Without Swapping Data? <\/h2>\n

In this problem, we will be discussing how we can swap nodes directly by changing links rather than swapping out the data. We will be given a linked list<\/a> and two keys say x and y, and we have to swap the nodes of the linked list having these keys as data.<\/p>\n

Note:<\/strong> All the keys in the linked list are unique, i.e. no two nodes in the linked list will have the same data.<\/p>\n

Understanding How swapping nodes in a linked list Works<\/h3>\n

Let\u2019s try to understand what the actual problem is, so basically here, we will be given a linked list and two keys x and y. We will have to iterate the linked list and search for the nodes with keys x and y. Once we got the nodes with the keys x and y, we will have to swap these nodes. We can swap nodes of linked list either by swapping their data or by changing the links (swapping nodes). Here we will be swapping the nodes by changing the links of the nodes.<\/p>\n

Input:<\/strong> <\/p>\n

\"\"<\/p>\n

Keys are 2 and 4 (x=2 and y=4).<\/p>\n

Output (After swapping the nodes):<\/strong> <\/p>\n

\"\"<\/p>\n

Which method of swapping is more efficient, swapping by data or swapping by nodes?<\/p>\n

In LinkedList, if we have to swap the data of two nodes, it\u2019s easy if there are fewer fields, and it would also take less time but if the data inside the nodes is large then swapping that amount of data can limit the speed of the process. For this reason, swapping nodes is preferred. <\/p>\n

Now let\u2019s move to the approach section, there we will see how we will solve the above problem of searching the nodes and swapping.<\/p>\n

Approach to swap two nodes in linked list without swapping data<\/h2>\n

Swapping nodes seem easy if the nodes to be swapped are adjacent, but then it becomes difficult for the following cases: <\/p>\n

    \n
  • The first case is when x and y are not adjacent.<\/li>\n
  • Or may be either of x and y is head nodes.<\/li>\n
  • Or maybe either x or y is the last node.<\/li>\n
  • And there can be a case where x and\/or y may not even be present in the linked list.<\/li>\n<\/ul>\n

    The idea is to search for the two nodes with keys x and y, if any of them is not present then return null otherwise change the next pointers of the two nodes.<\/p>\n

    Algorithm to swap the nodes in a linked list without swapping data<\/h2>\n
      \n
    • Search for x and y nodes in the LinkedList.<\/li>\n
    • If any of them is NULL, return.<\/li>\n
    • Take 4 pointers as previousX<\/strong>, currentX<\/strong>, previousY<\/strong>, currentY<\/strong> to denote the previous and current nodes of x and y respectively.<\/li>\n
    • If x is not head of the linked list, then change previousX->next = currentY and if x is head of the linked list then make node y as the new head of the linked list.<\/li>\n
    • If y is not head of the linked list, then change previousY->next = currentX and if y is the head of the linked list then make node x as the new head of the linked list.<\/li>\n
    • Finally, swap the next pointers of the current nodes as currentX->next to currentY->next.<\/li>\n<\/ul>\n

      Dry Run <\/h3>\n

      Let me dry run this for a small test case, then it will be much clearer to understand. In the following example, we have a linked list, and we need to swap the two nodes having keys as 2 and 4.
      \n\"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      Code Implementation<\/h3>\n\t\t\t\t\t\t