{"id":2060,"date":"2024-03-03T17:00:00","date_gmt":"2024-03-03T17:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2060"},"modified":"2024-03-04T08:09:52","modified_gmt":"2024-03-04T08:09:52","slug":"swap-nodes-in-pairs","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/swap-nodes-in-pairs\/","title":{"rendered":"Swap Nodes in Pairs Problem (C++, Java, Python)"},"content":{"rendered":"\n

Linked List is the most important topic that is asked in interviews and students find it a bit difficult than other data structures. One of them is reversing a linked list<\/a>, and finding the even position elements. In this article, we will discuss the Swap Nodes in Pairs problem, which is based on a linked list.<\/p>\n\n\n\n

Swap Nodes in Pairs Problem Explained<\/strong><\/h2>\n\n\n\n

In the Swap Nodes in Pairs problem, you are given a linked list. You have to return the list by swapping every two adjacent elements. Let\u2019s understand this with an example.<\/strong><\/p>\n\n\n\n

\"Swap<\/figure>\n\n\n\n

As we can see after swapping the adjacent elements we will get the resultant list.<\/p>\n\n\n\n

Brute Force Approach<\/strong><\/h2>\n\n\n\n

The brute force approach to solve this problem is to store all the values of the linked list<\/a> in an array. Now iterate over the array and swap every two adjacent elements. Now again from the linked list from the given array. The resultant list will be our answer.<\/strong><\/p>\n\n\n\n

Let\u2019s examine this approach step by step:<\/p>\n\n\n\n

    \n
  1. First, create a vector v. <\/li>\n\n\n\n
  2. Iterate over the given linked list and store the values of the list in the array.<\/li>\n\n\n\n
  3. Swap the adjacent pairs.<\/li>\n\n\n\n
  4. Now for the new linked list from the given array.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above code is O(n) where n is the total number of nodes in the linked list. The space complexity is O(n) as we are storing the values in the array whose size will be the same as the total number of nodes.<\/p>\n\n\n\n

    Iterative Approach<\/strong><\/h2>\n\n\n\n

    In the above approach, we are storing values in the array, which increases our time complexity from O(1) to O(n). In this approach, we will iterate over the linked list, swap the adjacent pairs at the same time, and move to the next node.\u00a0 <\/p>\n\n\n\n

    We first iterate over the list and swap the pairs if they exit. Then, move to the next to next node and repeat the same process until we reach the NULL node or reach the last node.<\/p>\n\n\n\n

    The time complexity for the above approach is O(n) as we are iterating over the whole linked list. The space complexity is O(1) as we are not using extra space to store the values of the linked list.<\/p>\n\n\n\n

    Recursive Approach<\/strong><\/h2>\n\n\n\n

    The above approach can also be solved recursively. Find out the differences between iteration and recursion here<\/a>.<\/p>\n\n\n\n

    We can Recursively call the reverse function for the next-to-next node of the current node, swap the current node and the node adjacent to it, and add the recursively returned list to the node next to the current one.<\/p>\n\n\n\n

    Let\u2019s examine the step-by-step approach:<\/p>\n\n\n\n

      \n
    1. First, check if we are at the last node or null node then return the current node.<\/li>\n\n\n\n
    2. Now recursively call function for next to next node and store the value in temp node.<\/li>\n\n\n\n
    3. Swap the current node and the node next to it. Made the next pointer point to the temp address.<\/li>\n\n\n\n
    4. Return the updated list.<\/li>\n<\/ol>\n\n\n\n
      \"Swap<\/figure>\n\n\n\n

      Let\u2019s now come down to writing the code.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is the C++ program to Swap Nodes in Pairs for Linked List:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\nusing namespace std;\n\nclass node{\n    public:\n    int data;\n    node* next;\n\n    node(int x){\n        data = x;\n        next = NULL;\n    }\n};\n\nnode* swap_pair(node* head){\n    if(head == NULL || head->next == NULL) return head;\n\n    node* temp = swap_pair(head->next->next);\n    node* temp1 = head->next;\n    head->next->next = head;\n    head->next = temp;\n    head = temp1;\n    return head;\n}\n\nint main(){\n\n    node* head = new node(1);\n    head->next = new node(2);\n    head->next->next = new node(3);\n    head->next->next->next = new node(4);\n\n    head = swap_pair(head);\n\n    \/\/ print the linked list\n    while(head){\n        cout<<head->data<<" ";\n        head = head->next;\n    }\n    return 0;\n}<\/pre><\/div>\n\n\n\n
      Java Code\u00a0<\/strong><\/h3>\n\n\n\n
      We can implement it in Java also:<\/p>\n\n\n\n
      class Node {\n    int data;\n    Node next;\n\n    Node(int x) {\n        data = x;\n        next = null;\n    }\n}\n\npublic class Main {\n    static Node swapPair(Node head) {\n        if (head == null || head.next == null) return head;\n\n        Node temp = swapPair(head.next.next);\n        Node temp1 = head.next;\n        head.next.next = head;\n        head.next = temp;\n        head = temp1;\n        return head;\n    }\n\n    public static void main(String[] args) {\n        Node head = new Node(1);\n        head.next = new Node(2);\n        head.next.next = new Node(3);\n        head.next.next.next = new Node(4);\n\n        head = swapPair(head);\n\n        \/\/ print the linked list\n        while (head != null) {\n            System.out.print(head.data + " ");\n            head = head.next;\n        }\n    }\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      You can even use Python to implement the recursive approach:<\/p>\n\n\n\n
      class Node:\n    def __init__(self, x):\n        self.data = x\n        self.next = None\n\ndef swap_pair(head):\n    if head is None or head.next is None:\n        return head\n\n    temp = swap_pair(head.next.next)\n    temp1 = head.next\n    head.next.next = head\n    head.next = temp\n    head = temp1\n    return head\n\nif __name__ == "__main__":\n    head = Node(1)\n    head.next = Node(2)\n    head.next.next = Node(3)\n    head.next.next.next = Node(4)\n\n    head = swap_pair(head)\n\n    # print the linked list\n    while head:\n        print(head.data, end=" ")\n        head = head.next<\/pre><\/div>\n\n\n\n
      Output:<\/strong> <\/p>\n\n\n\n
      2 1 4 3<\/code><\/pre>\n\n\n\n
      The time complexity for the recursive approach to solve Swap Nodes in Pairs problem is O(n) since we are traversing each node of the linked list. The space complexity is O(1) as we are not utilizing any additional space.<\/p>\n\n\n\n
      Here is a comparison of all the approaches:<\/p>\n\n\n\n
      Approach<\/strong><\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th>Description<\/strong><\/th><\/tr><\/thead>
      Brute Force<\/td>O(n)<\/td>O(n)<\/td>We are storing the values of nodes in the array. Which laid to O(n) space complexity<\/td><\/tr>
      Iterative Approach<\/td>O(n)<\/td>O(1)<\/td>We are iteratively moving to the next node of the linked list.<\/td><\/tr>
      Recursive Approach<\/td>O(n)<\/td>O(1)<\/td>We are recursively moving from the next to the next node and swapping the adjacent pairs.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we have seen various approaches to solve the leetcode problem<\/a> of Swap Nodes in Pairs for a Linked List with implementation in C++, Java, and Python. This is a very interesting question that was asked in many technical interviews. We had seen how we approach the problem recursively and iteratively. We also compared the time complexity of both approaches.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Understand what is the Swap Nodes in Pairs Problem. Learn how to solve it using 3 different approaches along with codes.<\/p>\n","protected":false},"author":14,"featured_media":2062,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2060","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2060","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2060"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2060\/revisions"}],"predecessor-version":[{"id":2140,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2060\/revisions\/2140"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2062"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2060"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2060"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2060"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}