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:
if not head or not head.next:
return head
next_node = head.next
head.next = self.swapPairs(next_node.next)
next_node.next = head
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
/**
* Definition for singly-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 {
public ListNode swapPairs(ListNode head) {
// if there are no nodes or only one node, return head
if (head == null || head.next == null) {
return head;
}
// initialize pointers for first and second nodes
ListNode first = head;
ListNode second = head.next;
// save reference to second node so we can return it
ListNode newHead = second;
// 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
return newHead;
}
}# 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 head is None or head.next is None:
# return head
# dummy = ListNode(0)
# dummy.next = head
# 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
if not head or not head.next:
return head
first_node = head
second_node = head.next
first_node.next = self.swapPairs(second_node.next)
second_node.next = first_node
return second_nodevar swapNodes = function(head, v1, v2) {
if (v1 === v2) return head;
var dummy = new ListNode(0);
dummy.next = head;
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;
};/**
* Definition for singly-linked list.
* 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* swapPairs(ListNode* head) {
// Base case
if (head == nullptr || head->next == nullptr) {
return head;
}
// Recursive case
ListNode* first = head;
ListNode* second = head->next;
first->next = swapPairs(second->next);
second->next = first;
return second;
}
};/**
* Definition for singly-linked list.
* 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 {
public ListNode SwapPairs(ListNode head) {
// check for empty or single node list
if (head == null || head.next == null) {
return head;
}
// create a dummy head node to simplify logic
ListNode dummyHead = new ListNode(0, head);
ListNode current = dummyHead;
// 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;
}
return dummyHead.next;
}
}