# Solution For Swapping Nodes In A Linked List

Problem Statement:

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4] Output: [2,1,4,3]

Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [1] Output: [1]

Constraints:
• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Solution approach:

In this problem, we have to swap every two adjacent nodes in a linked list. We can solve this problem recursively by swapping the next two nodes and then recursively calling the function to swap the remaining nodes.

We consider the following cases:

• If the list is empty or has only one node, we return the head of the list.
• For two nodes, we swap the nodes and return the new head of the list.
• For more than two nodes, we swap the first two nodes, and then recursively call the function to swap the remaining nodes.

Step 1: Initialize a recursive function that takes the head of the list as an argument.

Step 2: If the list is empty or has only one node, return the head of the list.

Step 3: Set the next node and the next to next node of the current node and swap them.

Step 4: Recursively call the function with the next to the next node as an argument.

Step 5: Return the next node as the new head of the list.

Python Code:

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

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:

return next_node

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the linked list. This is because we have to traverse all the nodes in the list once.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the number of nodes in the linked list. This is because we are using a recursive stack to swap the nodes.

## Step by Step Implementation For Swapping Nodes In A Linked List

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {

// if there are no nodes or only one node, return head
}

// initialize pointers for first and second nodes

// save reference to second node so we can return it

// while there are still nodes to swap
while (second != null) {

// swap pointers for first and second nodes
ListNode temp = second.next;
second.next = first;
first.next = temp;

// if there are no more nodes to swap, break out of loop
if (temp == null || temp.next == null) {
break;
}

// otherwise, update first and second pointers
first = temp;
second = temp.next;
}

// return new head of list
}
}
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:

# dummy = ListNode(0)
# current = dummy

# while current.next is not None and current.next.next is not None:
#     first = current.next
#     second = current.next.next
#     current.next = second
#     first.next = second.next
#     second.next = first
#     current = current.next.next

# return dummy.next

first_node.next  = self.swapPairs(second_node.next)
second_node.next = first_node

return second_node
var swapNodes = function(head, v1, v2) {
if (v1 === v2) return head;

var dummy = new ListNode(0);
var prev1 = null, curr1 = dummy;

while (curr1.next !== null && curr1.next.val !== v1) {
prev1 = curr1;
curr1 = curr1.next;
}

var prev2 = null, curr2 = dummy;

while (curr2.next !== null && curr2.next.val !== v2) {
prev2 = curr2;
curr2 = curr2.next;
}

if (curr1.next === null || curr2.next === null) return head;

if (prev1 !== null) prev1.next = curr2.next;
else dummy.next = curr2.next;

if (prev2 !== null) prev2.next = curr1.next;
else dummy.next = curr1.next;

var temp = curr1.next.next;
curr1.next.next = curr2.next.next;
curr2.next.next = temp;

return dummy.next;
};
/**
* 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:
// Base case
}

// Recursive case

first->next = swapPairs(second->next);
second->next = first;

return second;
}
};
/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
// check for empty or single node list
}

// create a dummy head node to simplify logic

// iterate through list, swapping nodes in pairs
while (current.next != null && current.next.next != null) {
ListNode first = current.next;
ListNode second = current.next.next;
first.next = second.next;
current.next = second;
current.next.next = first;
current = current.next.next;
}