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,

1. 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.
2. 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.
3. 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.