December 08, 2020
Hello fellow devs 👋! In this post, we will discuss another linked list problem.
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes. Only nodes itself may be changed.
Node.val
≤ 100Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
We are given a linked list and we need to swap nodes in pairs. What this means is that at a time we take two nodes and swap them, then take next two nodes and then swap them. This will go on until all the nodes are left.
The constraint is that we cannot update the data in the nodes. We can only change the node pointers appropriately to solve this problem.
We can follow below steps —
dummy
node whose next pointer will point to the current head.current
node which will be used to traverse the listfirst = current.next
and second = current.next.next
.first
to the next of second
which is actually the thirst node from the current.dummy.next
.Since we are traversing all the nodes of the linked list, the time complexity will be O(n).
Since we are not using any data structure for intermediate computations, therefore, the space complexity will be O(1).
public class SwapNodesInPairs {
public ListNode swapPairs(ListNode head) {
// Dummy node
ListNode dummy = new ListNode(0);
// Point the next of dummy node to the head
dummy.next = head;
// This node will be used to traverse the list
ListNode current = dummy;
// Loop until we reach to the second last node
while (current.next != null && current.next.next != null) {
// First node of the pair
ListNode first = current.next;
// Second node of the pair
ListNode second = current.next.next;
// Point the next of first node to the node after second node
first.next = second.next;
// Now the current node's next should be the second node
current.next = second;
// Linking the original second node to the first node
current.next.next = first;
// Move the pointer two nodes ahead
current = current.next.next;
}
return dummy.next;
}
}
class SwapNodesInPairs:
def swapPairs(self, head: ListNode) -> ListNode:
# Dummy node
dummy = ListNode(0)
# Point the next of dummy node to the head
dummy.next = head
# This node will be used to traverse the list
current = dummy
# Loop until we reach to the second last node
while current.next is not None and current.next.next is not None:
# First node of the pair
first = current.next
# Second node of the pair
second = current.next.next
# Point the next of first node to the node after second node
first.next = second.next
# Now the current node's next should be the second node
current.next = second
# Linking the original second node to the first node
current.next.next = first
# Move the pointer two nodes ahead
current = current.next.next
return dummy.next
var swapPairs = function (head) {
// Dummy node
const dummy = new ListNode(0);
// Point the next of dummy node to the head
dummy.next = head;
// This node will be used to traverse the list
let current = dummy;
// Loop until we reach to the second last node
while (current.next !== null && current.next !== undefined && current.next.next !== null) {
// First node of the pair
let first = current.next;
// Second node of the pair
let second = current.next.next;
// Point the next of first node to the node after second node
first.next = second.next;
// Now the current node's next should be the second node
current.next = second;
// Linking the original second node to the first node
current.next.next = first;
// Move the pointer two nodes ahead
current = current.next.next;
}
return dummy.next;
};
class SwapNodesInPairs {
fun swapPairs(head: ListNode?): ListNode? {
// Dummy node
val dummy = ListNode(0)
// Point the next of dummy node to the head
dummy.next = head
// This node will be used to traverse the list
var current: ListNode? = dummy
// Loop until we reach to the second last node
while (current!!.next != null && current.next!!.next != null) {
// First node of the pair
val first = current.next
// Second node of the pair
val second = current.next!!.next
// Point the next of first node to the node after second node
first!!.next = second!!.next
// Now the current node's next should be the second node
current.next = second
// Linking the original second node to the first node
current.next!!.next = first
// Move the pointer two nodes ahead
current = current.next!!.next
}
return dummy.next
}
}
Congratulations 👏! We have solved another linked list problem.
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.
Till next time… Happy coding 😄 and Namaste 🙏!