# Solution For Swap Nodes In Pairs

The Swap Nodes in Pairs problem on Leetcode is a problem that requires swapping every two adjacent nodes in a linked list, and returning the modified list.

Here is a detailed solution to the problem:

First, we need to understand the structure of a singly linked list. A singly linked list is a sequence of nodes, with each node containing a value and a pointer to the next node in the list. The head node is the first node in the list, and the tail node is the last node in the list, with its pointer pointing to NULL.

The problem requires us to swap every two adjacent nodes in the linked list. In other words, if we have a linked list like this:

1 -> 2 -> 3 -> 4 -> 5

We need to modify it to:

2 -> 1 -> 4 -> 3 -> 5

To solve the problem, we can create a new linked list and swap every pair of adjacent nodes from the original linked list. This requires iterating over the original linked list and creating a new node for each swapped pair in the new linked list.

Here is the step-by-step algorithm to solve the problem:

1. Create a new empty linked list.
2. Initialize a pointer “prev” to NULL, which will track the last node in the new linked list.
3. Initialize a pointer “curr” to the head of the original linked list.
4. Iterate over the original linked list, swapping every pair of adjacent nodes.
5. For each pair of adjacent nodes (let’s call them node1 and node2), swap them by updating their next pointers:
a. Set node1’s next pointer to node2’s next pointer
b. Set node2’s next pointer to node1
6. Connect the swapped pair of nodes to the new linked list by updating the pointers of the nodes in the new linked list:
a. If prev is not NULL, then set prev’s next pointer to node2 (the second node of the swapped pair).
b. Otherwise, set the head of the new linked list to node2 (the second node of the swapped pair).
7. Update prev to be node1 (the first node of the swapped pair).
8. Update curr to be the next node in the original linked list (which is node1’s original next pointer).

9. Repeat steps 4-8 until we reach the end of the original linked list.

Here is the implementation of the solution in Python:

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# Step 1: Create a new empty linked list
dummy = ListNode(0)
# Step 2: Initialize a pointer “prev” to NULL
prev = dummy
# Step 3: Initialize a pointer “curr” to the head of the original linked list

``````    # Step 4: Iterate over the original linked list, swapping every pair of adjacent nodes
while curr and curr.next:
# Step 5: Swap the pair of nodes
node1 = curr
node2 = curr.next
node1.next = node2.next
node2.next = node1

# Step 6: Connect the swapped pair of nodes to the new linked list
prev.next = node2

# Step 7: Update prev to be node1
prev = node1

# Step 8: Update curr to be the next node in the original linked list
curr = node1.next

return dummy.next
``````

The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because we make a single pass over the original linked list. The space complexity of the solution is O(1), since we use only constant extra space.

## Step by Step Implementation For Swap Nodes In Pairs

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
// if head is null or there is only one node in the linked list
}

// we will need to keep track of the previous node
// so that we can connect the swapped nodes later
ListNode prev = null;

// we will also need a reference to the current head
// so that we can return it later

// we will use a while loop to iterate through the linked list
// we will need to keep track of the next node
// so that we do not lose track of any nodes

// now we can swap the nodes

// if this is the first swap, we need to update the currHead
if(prev == null) {
}
// otherwise, we need to connect the previous node to the swapped nodes
else {
}

// finally, we need to update prev and head
}

// we will return the currHead which should now be pointing to the first swapped node
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# if there are no nodes or only one node, return head
# create a new head for the list
# set the first node's next to the third node
# set the second node's next to the first node
# recursively call the function on the remaining nodes
# return the new head of the list
```var swapPairs = function(head) {
// if the list has no nodes or only one node, return the list as is
}

// initialize pointers for current node, next node, and previous node
let prev = null;

// loop through the list, swapping nodes in pairs
while (curr && next) {
// if this is the first node in the list, update head to point to the next node
if (!prev) {
} else {
// otherwise, connect the previous node to the next node
prev.next = next;
}

// swap the next node and the current node
curr.next = next.next;
next.next = curr;

// update previous node to be the current node
prev = curr;

// update the current node and next node to be the next nodes in the list
curr = curr.next;
next = curr ? curr.next : null;
}

};```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
}

ListNode* dummy = new ListNode(0);
ListNode* current = dummy;

while(current->next != nullptr && current->next->next != nullptr) {
ListNode* first = current->next;
ListNode* second = current->next->next;

current->next = second;
first->next = second->next;
second->next = first;

current = first;
}

return dummy->next;
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
//if the list is empty or consists of only one node, return it
}

//store the first node in a temporary variable

//store the second node in a temporary variable

//set the first node to point to the third node

//set the second node to point to the first node
temp2.next = temp;

//set the first node to point to the second node