Problem

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.)

Examples

Example 1:

---
title: Input
---

graph LR;
1 --> 2:::focus --> 3 -->4:::focus

classDef focus fill:#f96
  
---
title: Output
---
graph LR;
2:::focus --> 1 --> 4:::focus -->3

classDef focus fill:#f96
  
Input: head = [1,2,3,4]
Output: [2,1,4,3]

Solution

There can be a lot of edge cases. So, it is good to use dummy head.

Method 1 - Iterative

Code

Java
public ListNode swapPairs(ListNode head) {
	if (head == null || head.next == null)
		return head;

	ListNode dummy = new ListNode(0);
	dummy.next = head;

	ListNode curr = head;
	ListNode prev = dummy;
	// we need 2 nodes to swap
	while(curr!=null && curr.next!=null){
		ListNode first = curr;
		ListNode second = curr.next;
		ListNode next = curr.next.next;
		
		// reverse first and second
		second.next = first;
		first.next = next;
		prev.next = second;


		prev = curr;
		curr = next;
	}
	return dummy.next;
}

Method 2 - Recursion

Code

Java
public ListNode swapPairs(ListNode head) {
	// base case - not enough nodes to swap
	if (head == null || head.next == null) {
		return head;
	}
	ListNode first = head; // first is useless variable as it is same as head, but used for clarity
	ListNode second = head.next;
	ListNode next = second.next;

	second.next = first;
	first.next = swapPairs(next);

	return second;
}

Here is example of above code: