Leetcode 24. Swap Nodes in Pairs
Problem Explanation
We have been provided with a singly linked list and the task here is to swap the nodes pairwise. For example, given a linked list 1 -> 2 -> 3, we want to swap the values pairwise i.e. the final linked list will look like 2 -> 1 -> 3.
In the output linked list, the first node is the second node of the input list, followed by the first node. Hence, the nodes are swapped pairwise. Note that we are only allowed to change the nodes themselves and not the values in the nodes.
Let's take another example. If the input linked list is 1 -> 2 -> 3 -> 4, then after swapping nodes pairwise, the output linked list will be 2 -> 1 -> 4 -> 3.
Approach
The problem can be solved by using a iterative approach. Here are the detailed steps,
- Initialize a dummy node whose next is pointing to the head of the linked list. Create two additional pointers, one for the previous node and the other for the current node.
- Run a loop for length of the linked list divided by 2.
- curr's next_pointer is switched to the node after its adjacent node.
- next's next_pointer is switched to the node before prev's next node.
- prev's next_pointer is switched to next.
- Lastly, move the prev pointer to curr and curr to the node next to it.
- Finally, return the next node of dummy which represents the new head of the linked list.
Algorithm Illustration
Consider a linked list 1 -> 2 -> 3 -> 4
Initialize a dummy node, prev pointer and curr pointer
1 2 3dummy = 0 -> 1 -> 2 -> 3 -> 4 4prev = 0 5curr = 1
After the 1st iteration, list would look like:
1 2 3dummy = 0 -> 2 -> 1 -> 3 -> 4 4prev = 1 5curr = 3
After the 2nd iteration, list would look like:
1 2 3dummy = 0 -> 2 -> 1 -> 4 -> 3 4prev = 3 5curr = null
Python Solution
1 2python 3class Solution: 4 def swapPairs(self, head: ListNode) -> ListNode: 5 # define a dummy node 6 dummy = ListNode(0) 7 dummy.next = head 8 9 prev_node = dummy 10 while head and head.next: 11 # nodes to be swapped 12 first_node = head 13 second_node = head.next 14 15 # swapping 16 prev_node.next = second_node 17 first_node.next = second_node.next 18 second_node.next = first_node 19 20 # reinitializing the head and prev_node for next swap 21 prev_node = first_node 22 head = first_node.next 23 24 # return the new head node 25 return dummy.next
Java Solution
1 2java 3public class Solution { 4 public ListNode swapPairs(ListNode head) { 5 ListNode dummy = new ListNode(0); 6 dummy.next = head; 7 ListNode prevNode = dummy; 8 while (head != null && head.next != null) { 9 10 // Nodes to be swapped 11 ListNode firstNode = head; 12 ListNode secondNode = head.next; 13 14 // Swap nodes 15 prevNode.next = secondNode; 16 firstNode.next = secondNode.next; 17 secondNode.next = firstNode; 18 19 // reinitzialing the head and prevNode for next swap 20 prevNode = firstNode; 21 head = firstNode.next; 22 } 23 return dummy.next; 24 } 25}
JavaScript Solution
1 2javascript 3var swapPairs = function(head) { 4 const dummy = new ListNode(0); 5 dummy.next = head; 6 let prev = dummy; 7 8 while (head !== null && head.next !== null) { 9 let firstNode = head; 10 let secondNode = head.next; 11 12 // swap 13 prev.next = secondNode; 14 firstNode.next = secondNode.next; 15 secondNode.next = firstNode; 16 17 // re-initzalizing the head and prev for next swap 18 prev = firstNode; 19 head = firstNode.next; 20 } 21 return dummy.next; 22}
C++ Solution
1 2cpp 3class Solution { 4public: 5 ListNode* swapPairs(ListNode* head) { 6 ListNode *dummy = new ListNode(0); 7 dummy->next = head; 8 ListNode *prev = dummy; 9 10 while (head != NULL && head->next != NULL) { 11 ListNode *firstNode = head; 12 ListNode *secondNode = head->next; 13 14 // swap 15 prev->next = secondNode; 16 firstNode->next = secondNode->next; 17 secondNode->next = firstNode; 18 19 // re-initializing head and prev for next swap 20 prev = firstNode; 21 head = firstNode->next; 22 } 23 return dummy->next; 24 } 25};
C# Solution
1 2csharp 3public class Solution { 4 public ListNode SwapPairs(ListNode head) { 5 ListNode dummy = new ListNode(0); 6 dummy.next = head; 7 ListNode prev = dummy; 8 while (head != null && head.next != null) { 9 ListNode firstNode = head; 10 ListNode secondNode = head.next; 11 12 // Swap 13 prev.next = secondNode; 14 firstNode.next = secondNode.next; 15 secondNode.next = firstNode; 16 17 // Re-initializing the head and prev for next swap 18 prev = firstNode; 19 head = firstNode.next; 20 } 21 return dummy.next; 22 } 23}
I hope the explanation is clear. You can use different programming languages to solve the problem as per your convenience using the algorithms mentioned above. The code provided is very straightforward and it follows the methodologies discussed above. You need to be careful with the pointers to get it right.
R Solution
Though it is not as common as Python or Java, R is also used for linked list operations, including this one. The R language is widely used in data analysis and machine learning, with an increasing interest in more complex data structures like linked lists.
Let's see how we can implement this solution in R.
1
2R
3swapPairs <- function(head) {
4 dummy <- list(val = 0, next = head)
5 prev <- dummy
6
7 while(!is.null(head$next)) {
8 firstNode <- head
9 secondNode <- head$next
10
11 # Swap nodes
12 prev$next <- secondNode
13 firstNode$next <- secondNode$next
14 secondNode$next <- firstNode
15
16 # Re-initializing the head and prev for the next swap
17 prev <- firstNode
18 head <- firstNode$next
19 }
20 dummy$next
21}
Scala Solution
Scala is often used in the software industry due to its efficiency, support for object-oriented and functional programming styles, and strong static types. Therefore, it's worth learning how to implement this solution in Scala as well.
1 2Scala 3class ListNode(var _x: Int = 0) { 4 var next: ListNode = null 5 var x: Int = _x 6} 7 8object Solution { 9 def swapPairs(head: ListNode): ListNode = { 10 val dummy = new ListNode(0) 11 dummy.next = head 12 var prev = dummy 13 14 while (head != null && head.next != null) { 15 val firstNode = head 16 val secondNode = head.next 17 18 // swap 19 prev.next = secondNode 20 firstNode.next = secondNode.next 21 secondNode.next = firstNode 22 23 // re-initializing head and prev for next swap 24 prev = firstNode 25 head = firstNode.next 26 } 27 dummy.next 28 } 29}
In code above, we start by creating a dummy node. Then we continuously swap pairs by changing pointers until we reach the end of the linked list. Finally, we return the head of the resulting list. This solution works in O(n) time complexity, where n is the number of nodes in the linked list, and O(1) space complexity, since we only used a constant extra space.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.